This is a program for getting the sum of prime numbers of given range. The problem is that it would take hours if the limit is about 1000000. I've read about the sieve of Eratosten but having difficulties with implementing it. Could someone help to make this piece of code working faster. Best regards.

``````#include <stdio.h>
#include <math.h>
void prime_num( int num)
{
double sum = 0;
bool isPrime=true;
for ( int i = 2; i <= num; i++)
{
for ( int j = 2; j <= num; j++)
{
if ( i!=j && i % j == 0 )
{
isPrime=false;
break;
}
}
if (isPrime)
{
printf("\nPrime: %d",i);
sum = sum + i;
}
isPrime=true;
}
printf("\nThe sum of primes is: %.0lf\n",sum);

}
int main(){
printf("Enter a number and I will generate the prime numbers up to that number: ");
int num = 0;
scanf("%d",&num);
prime_num(num);
return 0;
}``````

All 2 Replies

A couple big time savers:

1) You only need to check a number up to (and including) the square root of that number. If the number is prime at that time, then it's prime.

2) increment your loop by 2 for the numbers to be checked for primeness. Even numbers can never be prime if they are higher than 2.

You can read up on the Sieve of Eratosthenes at Wikipedia.

Also, in your editor's options set the TAB key to add 4 SPACEs instead. All those TABs make the code harder to read.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.