Can this hold true ? If a number x has no divisor in the interval [2,x/2] , then x is prime.

Question

going to check that the number is prime or not. and i need short cut than tracing every x-1s

Answer 1

The shortest code for prime and memory efficiency I know is
if(num℅2==0 && num!=2)
{cout<<"composite"; return 0;}
else{
for(I=3;I<=sqrt(num);I+=2)
{
if(num℅I==0)
{
cout<<"composite";
return 0;
}
}
}
cout<<"prime";
return 0;

Answer 2

If I understand your question, you would to optimize your code to find if a number is prime without looping from 2 to x/2?

Answer 3

yes it is true.
there can be no divisors in range[x/2,x-1].
But better for prime if you find sqrt of number and check if any divisior lies in between 2 and the sqrt.

Answer 4

Finding a solution on the web I realized that you cannot avoid loops.
So, to determine if a number is prime you must use a loop to find a divisor (x%i==0).
But you can do some correction to perform this algorithm (assuming x is the number to test and i is the loop counter):
- dont loop every number from i=0 to i<x;
- stop the loop when i=x/i (and not 2 as my code);
- the best implementation is looping only primes;
This last point make me exciting because I already implemented this algorithm on my primeIterator class and now I will modify it as described above.. (now I'm not at home..)
In the next days I would test my class on a big server to see the time used to determine a prime near 2^20 after and before the changes!
Thank you for asking this question I found very interesting.

Answer 5

Hi @Megatron, I'm sorry but I cannot understand if your code would be run correctly..
If you start your for loop from 0 it would recognize as composite all numers.. or not? Please, tell me more..

Answer 6

@Michael
Sorry it was an error I didn't paid attention or might be due to this automatic Google keyboard that tries to correct things in weird manner. I corrected the mistake.

Answer 7

exactly.