Thread: Just a feeling...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    3

    Just a feeling...

    I wrote this program to help me find all the prime numbers from 2 to i. The results are good, but I feel that something goes wrong in the program. Could you help me? Is everything OK with that piece of code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char *argv[])
    {
      int i, j, k, n;
      printf("Give me the top number: \n");
      scanf("%d", &i);
      for (j=2;j<i;j++){
        for (k=2;k<i;k++)
        {
            n=j%k;
            if (n==0) break;
        }if (j==k) printf("%d:%d \n",j,k);}
      system("PAUSE");
      return 0;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You can eliminate half of your checks by incrementing by 2 each time, because even numbers aren't prime. Start at 3 instead, increment by 2. Also, search the forum for prime numbers, I'm sure you'll find tons of posts.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    * Start from 2. Test only odd numbers after that.
    * You should store all existing prime numbers and use them for following computations, instead of testing each number everytime.
    * Use the fact that if for all prime numbers p < sqrt(n), if none divide into n, then n is prime. Testing up to sqrt(n) is far quicker than testing up to n.

    Don't believe me, believe the numbers.
    Code:
    Clock cycles required to calculate primes up to n
    n			Yours				Mine
    10000		156					16
    100000		16031 (15 seconds!)	109
    1000000		lazy to run			2578

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I'd rather believe the code, instead of numbers you pull out of your ass.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. loop the loop - feeling foolish
    By estos in forum C Programming
    Replies: 2
    Last Post: 04-07-2007, 02:45 AM
  2. The feeling.......
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-16-2002, 04:20 AM
  3. PS: I gotta bad feeling about the file pointers!
    By lonelyplanetwanderer in forum C Programming
    Replies: 9
    Last Post: 07-01-2002, 06:07 AM
  4. That friday feeling
    By RobS in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 10-11-2001, 12:11 PM