Thread: prime numbers

  1. #1
    Unregistered
    Guest

    prime numbers

    I need some help. I need to see if a number entered is a prime number. Here is my code:

    Code:
    /* Check to see if a number is prime or not.
       A number is prime if it can only be dividied by itself and 1
       but by no other number.   */
    
    #include <stdio.h>
    
    int isPrime(int number)
    {
    
       int count;
       for (count=1; count<number; count++)
       {
          if (number % count == 0 ) return 1;
    
       }
       return 0;
    }
    
    int main()
    {
       int number;
    
       printf("Please enter a number ");
       if (scanf("%d", &number) != 1)
       {
          printf("Invalid number entered\n");
          return 1;
       }
    
       if (isPrime(number))
          printf("\n%d is prime\n", number);
       else
          printf("\n%d is not prime\n", number);
    
       return 0;
    }
    I cant seem to get the right results. What am i doing wrong? Please help
    thanks

  2. #2
    shaik786
    Guest
    >for (count=1; count<number; count++)
    You don't need to start the loop with 1, since any number can be divided by 1 and this function would always return(1) at the first step itself. Start it with 2 instead.

  3. #3
    Im back! shaik786's Avatar
    Join Date
    Jun 2002
    Location
    Bangalore, India
    Posts
    345
    .... had to enter my password again

  4. #4
    Unregistered
    Guest
    It sill doesnt work properly...

    Does it have something to do with th if statement in the for loop?

  5. #5
    Unregistered
    Guest
    thanks but i have tried that and it still doesnt work...

    When i do that it seems to return that odd numbers are all prim, which they arent. Any ideas ???

  6. #6
    Registered User moonwalker's Avatar
    Join Date
    Jul 2002
    Posts
    282

    dude..

    the reason why it is screwing up is because

    1)
    for (count=1; count<number; count++)
    if (number % count == 0 ) return 1;

    anything is divisible by 1, so change it to count = 2; ... ...


    2)
    when (number % count == 0) it means number is NOT prime
    ... so change return 1 to return 0 and return 0 to return 1


    hope this helps..

    GOOD LUCK.

  7. #7
    Registered User moonwalker's Avatar
    Join Date
    Jul 2002
    Posts
    282

    hmm

    here's the modified code..
    concentrate on the bold lines...

    Code:
    /* Check to see if a number is prime or not.
       A number is prime if it can only be dividied by itself and 1
       but by no other number.   */
    
    #include <stdio.h>
    
    int isPrime(int number)
    {
    
       int count;
       for (count=2; count<number; count++)
       {
          if (number % count == 0 ) 
          {
             return 0;
          }
    
       }
       return 1;
    }
    
    int main()
    {
       int number;
    
       printf("Please enter a number ");
       if (scanf("%d", &number) != 1)
       {
          printf("Invalid number entered\n");
          return 1;
       }
    
       if (isPrime(number) == 1)
          printf("\n%d is prime\n", number);
       else
          printf("\n%d is not prime\n", number);
    
       return 0;
    }
    you might also want to optimize your code... for example, the loop
    needn't go from count = 2 to count < number...

    if you have 7 ... for example, the loop can go till 7/2 (integer
    division) ... which is 3 ....
    if you cross 3, there won't be any factors anyways...

    this will save a lot of ****work when you're checking for huuge
    numbers like 100000001 ... it only needs to check till half of that
    number to see if it's prime or not..
    Last edited by moonwalker; 08-19-2002 at 11:54 PM.

  8. #8
    Unregistered
    Guest
    Here is my changed code

    Code:
    #include <stdio.h>
    
    int isPrime(int number)
    {
    
       int count;
       for (count=2; count<number; count++)
       {
          if (number % count == 0 ) return 0;
          else return 1;
    
       }
       /*return 0; */
    }
    
    int main()
    {
       int number;
    
       printf("Please enter a number ");
       if (scanf("%d", &number) != 1)
       {
          printf("Invalid number entered\n");
          return 1;
       }
    
       if (isPrime(number))
          printf("\n%d is prime\n", number);
       else
          printf("\n%d is not prime\n", number);
    
       return 0;
    }
    It still doesnt work. Did i change it properly?

  9. #9
    Registered User moonwalker's Avatar
    Join Date
    Jul 2002
    Posts
    282

    hmm

    read my above message... see my code..

    (in your latest code, you got confused where to put
    return... see my code and you'll understand)

  10. #10
    Unregistered
    Guest
    Thanks for that .
    I think i should get glasses.

  11. #11
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Code:
       for (count=2; count<number; count++)
       {
          if (number % count == 0 ) return 0;
          else return 1;
    
       }
    Note that when you enter the for-loop, the function always exits, because of the returns in the for-loop.

  12. #12
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490

    Re: hmm

    Originally posted by moonwalker
    here's the modified code..
    concentrate on the bold lines...
    [edited out]
    you might also want to optimize your code... for example, the loop
    needn't go from count = 2 to count < number...

    if you have 7 ... for example, the loop can go till 7/2 (integer
    division) ... which is 3 ....
    if you cross 3, there won't be any factors anyways...

    this will save a lot of ****work when you're checking for huuge
    numbers like 100000001 ... it only needs to check till half of that
    number to see if it's prime or not..
    i think you can check all numbers up to the square root of the number and still be on the safe side

  13. #13
    Registered User moonwalker's Avatar
    Join Date
    Jul 2002
    Posts
    282

    hmm

    you're right, i missed that.

    any non prime number will atleast have 3 factors (including 1, it's square root, and itself).
    So if a number has less than 3 factors (out of which 2 factors
    are 1 and itself), it's said to be a prime.

    if we cross square root of the number (int the for loop) and
    still didn't get factors (other than 1 and itself), it is definitely a prime.


    also, i found out that in the for loops, instead of saying

    for (i = 2; i <= sqrt(number); i++)

    we can first say

    tempvariable = sqrt(number);

    for (i = 2; i <= tempvariable; i++)

    that way, it need not calculate sqrt(number) so many times
    in the for loop... so it should run faster..
    Last edited by moonwalker; 08-20-2002 at 03:03 PM.

  14. #14
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    might as well add my suggestion to the pot...

    after you check for two, you only need to check every odd number after that since if, say, 8 were a factor, 2 will also be a factor

    if (number == 2) return 1;
    if (number % 2 == 0) return 0;

    for (...; ...; count += 2)
    .
    .
    .

  15. #15
    Registered User
    Join Date
    Sep 2001
    Location
    Fiji
    Posts
    212
    >>any non prime number will atleast have 3 factors (including 1, it's square root, and itself).

    sqrt(21) = 4.582575...

    not a factor of 21. A factor has to be an integer.

    [EDIT]

    Code:
    int isPrime(int n) {
        int c =0, s=0;
    
        if (n == 1) { return 0; }
        if (n == 2) { return 1; }
        if (n % 2 == 0) { return 0; }
    
        s = (int)sqrt( (double)n );
    
    	for (c=3; c < s; c+=2) {
            if (n % c == 0) {return 0;}
        }
        return 1;
    }
    [/EDIT]
    Last edited by kwigibo; 08-20-2002 at 08:42 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  3. More Prime Numbers
    By mmuhlenb in forum C Programming
    Replies: 3
    Last Post: 02-21-2003, 10:06 AM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM