how to detect a prime number?

The prime number is the natural number that only have two distinct natural dividers: 1 and itself.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97


The following is the code to detect if the given number n is prime number:

bool isPrime(unsigned n) {
unsigned sq = (unsigned) sqrt((float)n); //calculate the square root of n
for (int i = 2; i < = sq; i++) {
if( n% i == 0)
return false;
}
return true;
}

The complexity (O-notation) for the algorithm is O(sqrt(n))

1. Write a program to calculate the sum of the prime number less than N

unsigned sumPrime(unsigned n) {
unsigned sum = 0;
if(n <= 1)
return sum;
for(int i = 2; i <= n; i++){
if(isPrime(i))
sum += i;
}
return sum;
}

The complexity (O-notation) of the program is O(n*sqrt(n))

No comments:

Post a Comment