10 Replies - 711 Views - Last Post: 09 December 2015 - 08:50 AM

#1 straygrey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 04-October 08

C program to calculate prime numbers

Posted 06 December 2015 - 12:27 PM

I have written the following and now looking for peer review and constructive critism.
Is it correct and/or is there a better/simpler/faster way of doing the same thing?
#include <time.h>
#include <math.h>
int main()
    {
    unsigned long n, i=3, count=0, c, abcd = 3;
    long double launch, done, diff;
    launch = clock();
// Only checking from 2 to square root of number is sufficient
    for (abcd=3; abcd < 100000; abcd++)
        {
        for ( c = 2; c <= (int)sqrt(abcd); c++ )
            {
            if (abcd%c == 0) // Divisable so not a prime number
                {
                break;
                }
            else
                {
                if(c==(int)sqrt(abcd))
                    {
                    printf("%ld\n",abcd);
                    count++;
                    }
                }
            }
        }
    done = clock();
    diff = (done - launch) / CLOCKS_PER_SEC;
    printf("Number of Prime Numbers : %d\n",count);                            printf("Total time taken by CPU %Lf Clocks -  %Lf Clocks = %Lf seconds with CLOCKS_PER_SEC @ %d\n",done, launch, diff, CLOCKS_PER_SEC );
    return 0;
    }



Is This A Good Question/Topic? 0
  • +

Replies To: C program to calculate prime numbers

#2 andrewsw  Icon User is offline

  • Beach ready
  • member icon

Reputation: 5477
  • View blog
  • Posts: 21,543
  • Joined: 12-December 12

Re: C program to calculate prime numbers

Posted 06 December 2015 - 12:33 PM

Have you run it? Have you checked the results?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 4778
  • View blog
  • Posts: 15,780
  • Joined: 05-May 12

Re: C program to calculate prime numbers

Posted 06 December 2015 - 01:28 PM

Notice that 2 is the only even prime number. All other primes are odd. That means that from 3 onwards, you only need to check the odd numbers.

Also consider caching the prime numbers from the previous search. That way you can start at the next odd number.

Our even better find all primes less got the highest number first. That will fill the cache for all the lower numbers.
Was This Post Helpful? 1
  • +
  • -

#4 straygrey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 04-October 08

Re: C program to calculate prime numbers

Posted 07 December 2015 - 02:43 AM

Skydiver, thank you I forgot about 2 and have now made the alteration by starting count at 1 rather than 0.
I have also run it with the following results

Number of Prime Numbers : 9591
Total time taken by CPU 2244218.000000 Clocks - 5599.000000 Clocks = 2.238619 seconds with CLOCKS_PER_SEC @ 1000000

with abcd incremented by one. However after reading skydiver's reply I decided to try for odd numbers only, by incrementing abcd+=2 and as abcd starts at 3 I suspect this only includes odd numbers and now I get

Number of Prime Numbers : 9591
Total time taken by CPU 2225311.000000 Clocks - 4131.000000 Clocks = 2.221180 seconds with CLOCKS_PER_SEC @ 1000000

Not a stunning increase in speed. I expected more than that.

Now how do I confirm that there are 9591 prime numbers between 0 and 100000. I'll tried google and find that I must have missed another one as https://www.mathsisf...mber-lists.html says there 9592.
Back to the drawing board.

This post has been edited by straygrey: 07 December 2015 - 02:45 AM

Was This Post Helpful? 0
  • +
  • -

#5 andrewsw  Icon User is offline

  • Beach ready
  • member icon

Reputation: 5477
  • View blog
  • Posts: 21,543
  • Joined: 12-December 12

Re: C program to calculate prime numbers

Posted 07 December 2015 - 03:05 AM

By starting at 1 and stepping by 2 haven't you skipped 2?
Was This Post Helpful? 0
  • +
  • -

#6 straygrey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 04-October 08

Re: C program to calculate prime numbers

Posted 07 December 2015 - 03:19 AM

count is only used to contain the number of primes found but as abcd is started at 3 the numer two(2) is not included in the "algorithm" and therefore I have started count at 1 rather than 0 to allow for the "missing" two(2).
Is my thinking at fault?
Was This Post Helpful? 0
  • +
  • -

#7 no2pencil  Icon User is offline

  • Professor Snuggly Pants
  • member icon

Reputation: 6179
  • View blog
  • Posts: 29,756
  • Joined: 10-May 07

Re: C program to calculate prime numbers

Posted 07 December 2015 - 07:41 AM

View Poststraygrey, on 06 December 2015 - 02:27 PM, said:

[code]
if (abcd%c == 0) // Divisable so not a prime number
{
break;
}
else
{
...
}

If this were me, I would check if not equal to, & just not have a code block for the if equal to, as long as we're not taking any action.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 4778
  • View blog
  • Posts: 15,780
  • Joined: 05-May 12

Re: C program to calculate prime numbers

Posted 07 December 2015 - 08:36 AM

You are counting the time it takes to do a printf(). If you stash the values into an array, and then print out the values outside of your timing block you will find a much different experience.

Also, that break call in there seems to be a bug. By stopping at the first non prime number, you are not find the rest of the primes less than the square root of your target number.
Was This Post Helpful? 1
  • +
  • -

#9 straygrey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 04-October 08

Re: C program to calculate prime numbers

Posted 08 December 2015 - 12:55 AM

By commenting out the printf I get
Number of Prime Numbers : 9591
Total time taken by CPU 2233033.000000 Clocks - 5661.000000 Clocks = 2.227372 seconds with CLOCKS_PER_SEC @ 1000000

and, as far as my thinking goes, that break, if it is the same one we are speaking of, is stopping on the 1st time a number is found to be non-prime and then carrying on with the next.

This post has been edited by Skydiver: 09 December 2015 - 08:37 AM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 4778
  • View blog
  • Posts: 15,780
  • Joined: 05-May 12

Re: C program to calculate prime numbers

Posted 09 December 2015 - 08:37 AM

There is no need to quote the post above yours. Use the Reply button or the Fast Reply area.

Post the two versions of your code: the version without the optimizations and the version with the optimizations.
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 4778
  • View blog
  • Posts: 15,780
  • Joined: 05-May 12

Re: C program to calculate prime numbers

Posted 09 December 2015 - 08:50 AM

I see what you mean about using the break. The inner loop is essentially there to make sure that the target number abcd is prime.

You can also get a speed gain by computing sqrt(abcd) just one, instead of once in the for loop condition check and then another time in your deepest if statement.

May I suggest looking at the Sieve of Eratosthenes.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1