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.

  • $\begingroup$ Using this logic, you should have a divisibility test for each prime number up to $N$. I think this is almost impossible, and for sure very hard!... instead, why don't check the remainder of the division of each number by each prime? If the remainder is $0$, the you stop, otherwise you go on... $\endgroup$ – the_candyman Sep 8 '16 at 18:36
  • $\begingroup$ @the_candyman can you answer it and write an explanation of your method .your method seems to be better . $\endgroup$ – satyajeet jha Sep 8 '16 at 18:38
  • $\begingroup$ Not sure I understand what the question is. Not sure why you skipped over $7$ in your list of primes. I think, but am not certain, you are describing the Sieve of Eratosthenes which is an excellent technique for filtering by prime divisors. $\endgroup$ – lulu Sep 8 '16 at 18:45

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));


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.