least prime divisor of all numbers up to N=$100004$

Question

I need to find the least prime divisor of of all numbers up to N=$100004$

What i have done till now is :

Generated all prime numbers till N and if number is prime then its lpd is number itself . If number is not a prime then ,

1.check if it is even ,if found even then its lpd is 2 and we got it so don't need to check anything else . 2.check if it is divisible by 3 then its lpd is 3 and we got it so don't need to check anything else .. 3.check if it is divisible by 5 then its lpd is 5 and we got it so don't need to check anything else . 4.check if it is divisible by 11 then its lpd is 11

I tried the above algorithm but i doubt that i have missed some numbers which are not prime and divisible by numbers other than 2 ,3,5,11 so if there is any such number which i have missed,it would be great if you add them.

Answer 1

Suppose you have an array of size $100004$, where the element of the array at position $n$ is the least prime divisor of $n$. Initially, let all the values in the array be $0$.

Now, the following algorithm can be used. Traverse the elements of the array starting from the second element. At each element $x$, if the value in the array is $0$, then it is a prime. Then, run a loop starting from $x$ till $100004$ in increments of $x$. At each position $i$, if the value is $0$, i.e., no prime divisor smaller than the given divisor has divided the number $i$, then $x$ is its least prime divisor. Else, ignore that number.

Using the above algorithm, you can find the least prime divisors of all numbers needed. A modification that can be done is to traverse only upto $\sqrt{100004}$, as all numbers after that having no prime divisor less than or equal to $\sqrt{1000004}$ must be a prime, and their least prime divisor would be the number themselves.

The problem with your approach in the question is that you are checking only against a small set of primes. For numbers such as $49,91$ etc. the algorithm will fail.

Answer 2

Rather than checking the numbers one by one, it's best to loop over the primes and mark the multiples of that prime that are not already marked. Something like this Matlab code:

N = 100004;

P = primes(N);

A = inf*ones(1,N);

for p = P

 R = p*[1:N/p]; % these are the multiples of p that are <= N

 A(R) = min(p,A(R));

end