isPrime fun

[ehab93]

can anyone tell me what's wrong with this fun!!
it doesn't work with big numbers !

bool isPrime(long n, long count) {
		if (count >= n)
			return true;
		if (n % count == 0)
			return false;
		return isPrime(n, count+1);
	}

[vlad from moscow]

Show the call of the function with "big numbers".

[ehab93]

long sum = 0;
		for (long i = 2; i < 2000000; i++){
			if(isPrime(i,  2))
				sum += i;
		}

[ehab93]

it shows that error(in java)
java.lang.StackOverflowError

[vlad from moscow]

I think that the problem is that the function is recursive and the stack can not accommodate 2000000 - 1 calls of the function.

[ehab93]

So.. is there any other function that do the isPrime efficiently ..?

[vlad from moscow]

Simply rewrite it using a loop. Take also into account that it is enough to check divisors that less than or equal to sqrt( n )

[ehab93]

i do! .. this one

 bool isPrime(long n){
		for(int i = 2; i < n; i++){
			if (i == n)
				continue;
			if (n % i == 0)
				return false;
		}
		return true;
	}

but it never ends!!!

[vlad from moscow]

If you need the answer then the sum is equal to 142913828922

[ehab93]

thanks vlad ,, but i need the function :)

[vlad from moscow]

bool isPrime( long n )
{
	for( long i = 2; i * i  <= n; i++ )
	{
		if ( n % i == 0 ) return false;
	}
	return true;
}

[ehab93]

it works! ,, thank you @vlad :))

[vlad from moscow]

I compared the result gotten by executing this function and the result of my function and they coinsided.

142913828922
142913828922

[ehab93]

it gives me this 143042032116

[ehab93]

however, yours is the wright one.

[vlad from moscow]

Check the statement

for( long i = 2; i * i <= n; i++ )

[ehab93]

shouldn't it to be i < n , not = !!?
coz if it checks 2%2 == 0 , then it's nor prime!

[vlad from moscow]

I wrote the function. Can you yourself understand how it works?

[ehab93]

oh .. it's squrt n . .ok got it