Prime Number Checker:
isPrime
public static Boolean isPrime(int num){ //method signature. returns Boolean, true if number isPrime, false if not
if(num==2){ //for case num=2, function returns true. detailed explanation underneath
return(true);
}
for(int i=2;i<=(int)Math.sqrt(num)+1;i++){ //loops through 2 to sqrt(num). All you need to check- efficient
if(num%i==0){ //if a divisor is found, its not prime. returns false
return(false);
}
}
return(true); //if all cases don't divide num, it is prime.
}
Explanation: Very simple code. Few things to notice:
I loop through 2 to the sqrt(num) to check if these divide num. Much more efficient than from 2-> num-1, and always works. A number greater than the sqrt(num)=i such that n%i==0 does not matter because n/i<i and will already be checked. It reduces the complexity of the algorithm from O(n) to O(n^0.5). However, this scenario forces me to check n=2 seperately, because it will return false (2%2==0). Javascript implementation above to check prime-ness directly online. It is actually written with the algorithm from 2->num-1.
if(num==2){ //for case num=2, function returns true. detailed explanation underneath
return(true);
}
for(int i=2;i<=(int)Math.sqrt(num)+1;i++){ //loops through 2 to sqrt(num). All you need to check- efficient
if(num%i==0){ //if a divisor is found, its not prime. returns false
return(false);
}
}
return(true); //if all cases don't divide num, it is prime.
}
Explanation: Very simple code. Few things to notice:
I loop through 2 to the sqrt(num) to check if these divide num. Much more efficient than from 2-> num-1, and always works. A number greater than the sqrt(num)=i such that n%i==0 does not matter because n/i<i and will already be checked. It reduces the complexity of the algorithm from O(n) to O(n^0.5). However, this scenario forces me to check n=2 seperately, because it will return false (2%2==0). Javascript implementation above to check prime-ness directly online. It is actually written with the algorithm from 2->num-1.
Provided by website-hit-counters.com site. |