Why Python Sucks...Least Prime Factor- GFG

Nowadays, I am solving GFG Problems of the day and also it's medium level problems in general apart from that. Switching from CodeChef I feel that the difference in level is not that much it's just that the probs here are more related to the Data Structures part and also a thing about these probs is that they don't ever ask me to have the whole implementation, that is from taking the input all upto the result part like CodeChef, it's much like HackerRank although the level is far better than HackerRank.

This problem was part of the POTD( Problem of the Day ), and I took this right in the midnight when we get the problem and ofcourse there was nothing at all if we think about the idea it's all about the implementation part.

More than that, I feel that this was somewhat to remove the Python Programmers in the race bcz if someone would just be coding in Python then obviously they wouldn't have been able to solve this without racking their brain, but... not if you can also code in CPP, yeah that's me, I saw that only about 9 cases were left so it was most like to be passed in CPP and it just took me around 2 mins to code this in CPP, I wasn't 100 perc. sure that this would work but it did and this is so weird cause the problem is that even after using the best possible option like the sieve of eratosthenes method this didn't pass everything in Python, then what could I really do without doing this again in CPP.

This was with using Sieve of Erastosthenes Meth.

With the normal approach

Basically, I think that this is the price that we have to pay if we code just in Python, ofcourse it is slow, and also what do you expect after getting everything cooked for you whether it is the more than easier syntax of the lang or the built in functions like gcd and all.

This shows that how much it is imp to know atleast CPP ( no offense, Java is also fine, but... you know ) apart from Python.

I seriously feel that this problem should be solved without even thinking about the ideation part cause it is so direct, you can consider the cases mentioned below:-

while(True):

    if (sure about the implementation and idea):

            Solve it what are you waiting for...

            break

    elif( sure about the idea but not the implementation):

            Work on your Language Skills

            break

    else:

            c'mon! try to get out of the loop

             pass

Problem Statement:-

Given a number N, find the least prime factors for all numbers from 1 to N.  The least prime factor of an integer X is the smallest prime number that divides it.
Note :

• 1 needs to be printed for 1.
• You need to return an array/vector/list of size N+1 and need to use 1-based indexing to store the answer for each number.

Example 1:

Input: N = 6
Output: [0, 1, 2, 3, 2, 5, 2] 
Explanation: least prime factor of 1 = 1,
least prime factor of 2 = 2,
least prime factor of 3 = 3,
least prime factor of 4 = 2,
least prime factor of 5 = 5,
least prime factor of 6 = 2.
So answer is[1, 2, 3, 2, 5, 2]. 

Example 2:

Input: N = 4
Output: [0, 1, 2, 3, 2]
Explanation: least prime factor of 1 = 1,
least prime factor of 2 = 2,
least prime factor of 3 = 3,
least prime factor of 4 = 2.
So answer is[1, 2, 3, 2]. 

Your Task:  
You don't need to read input or print anything. Complete the function leastPrimeFactor() which takes N as input parameter and returns a list of integers containing all the least prime factors of each number from 1 to N.

Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)

Constraints:
2<= n <=105

CPP:-

bool isPrime(int num){

    for(int i=2;i<num;i++){

        if(num%i==0){

            return false;

        }

    }

    return true;

}

class Solution {

  public:

    vector<int> leastPrimeFactor(int n) {

        // code here

        /*

         def leastPrimeFactor (self, n):

        # code here

        ans=[0]*(n+1)

        ans[1]=1

        ans[2]=2

        def isPrime(num):

            for i in range(2,num):

                if(num%i==0):

                    return False

            return True

        for i in range(3,n+1):

            for j in range(2,i+1):

                if(i%j==0 and isPrime(j)):

                    ans[i]=j

                    break

        return ans

        */

        vector<int> ans(n+1,0);

        ans[1]=1;

        // ans[2]=2;

        for(int i=2;i<=n;i++){

            for(int j=2;j<=i;j++){

                if(i%j==0 && isPrime(j)){

                    ans[i]=j;

                    break;

                }

            }

           

        }

        return ans;

    }

};

Python:-

class Solution:

    def leastPrimeFactor (self, n):

        ''' Cannot Improve this code more for right now... '''

       

        # code here

        # If we create list like below or without creating append elems, both cases same TC, no change

        ans=[0]*(n+1)

        ans[1]=1

        ans[2]=2

       

        # 1081/1121 Passed

        # def isPrime(num):

        #     for i in range(2,num):

        #         if(num%i==0):

        #             return False

        #     return True

       

        # Trying a different approach to check for prime

        # 1112/1121 Passed

        import math

        def isPrime(n):

          for i in range(2,int(math.sqrt(n))+1):

            if (n%i) == 0:

              return False

          return True

         

        for i in range(3,n+1):

            for j in range(2,i+1):

                if(i%j==0 and isPrime(j)):

                    ans[i]=j

                    break

        return ans