+ 1

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

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

21st Jan 2017, 11:03 AM
WONDE-TOM + 2
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;
22nd Jan 2017, 3:14 AM
Megatron + 1
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?
21st Jan 2017, 11:17 AM
Michael Isac Girardi + 1
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.
21st Jan 2017, 11:55 AM
Megatron + 1
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.
21st Jan 2017, 5:54 PM
Michael Isac Girardi + 1
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..
23rd Jan 2017, 8:29 AM
Michael Isac Girardi + 1
@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.
23rd Jan 2017, 9:01 AM
Megatron 0
exactly.
21st Jan 2017, 1:46 PM
WONDE-TOM 