Thread: Simple question

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    3

    Simple question

    I'm new to C and have a question. This small program is used to test a number that the user enters and see if it is a prime number. Here is the code:

    Code:
    /* Prime number tester */
    
    #include <stdio.h>
    
    int main(void)
    
    {
    
      int num, i, is_prime;
    
      printf("Enter the number to test: ");
      scanf("%d", &num);
    
      /* now test for factors */
    
      is_prime = 1;
      for(i=2; i<=num/2; i=i+1)
        if((num%i)==0) is_prime = 0;
    
      if(is_prime==1) printf("The number is prime.");
      else printf("The number is not prime.");
    
      return 0;
    
    }
    My question is about the for statement here. I don't quite understand why it was needed in this program to accomplish the end result or what exactly it did there. I understand for statements in general, just not this particular one. Thanks in advance for your assistance.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Have you looked in a math book for the definition of prime?

  3. #3
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Your for loop goes through every integer up to half the number you are testing to see if it is a factor. If it is, then the number cannot be prime. Note that it is actually only necessary to go up to the square root of the number, not half of it, since no factor can be larger than the square root without having a corresponding smaller factor.

  4. #4
    Registered User
    Join Date
    Jan 2006
    Posts
    3
    Quote Originally Posted by Salem
    Have you looked in a math book for the definition of prime?
    Thanks for your assistance, but my question was not what is a prime number. I understand what a prime number is, my question was only was the particular for statement needed to acheive the end result.

  5. #5
    Registered User
    Join Date
    Jan 2006
    Posts
    3
    Quote Originally Posted by lemnisca
    Your for loop goes through every integer up to half the number you are testing to see if it is a factor. If it is, then the number cannot be prime. Note that it is actually only necessary to go up to the square root of the number, not half of it, since no factor can be larger than the square root without having a corresponding smaller factor.
    Thank you very much, it is clearer to me now.

  6. #6
    Registered User
    Join Date
    Dec 2005
    Location
    Australia - Melbourne
    Posts
    63
    the for statement is the most important part of your program- without it the answer will always be "the number is prime".

    basically it tests if your input (number) has any other factors other than one and those greater than half the number(includes itself). if there is i.e (num%i)==0 then the program will end up printing "the number is not a prime".

    your program prints that 1 is a prime, which it isn't.

    hope i've been a help

  7. #7
    Registered User
    Join Date
    Feb 2005
    Posts
    19
    Hello lleon,

    The program you posted is clever. I think the the "is_prime = 1" and "is_prime = 2" functions as boolean
    test operators (someone please correct me if I'm wrong.).

    I found a cool reference as to why the number 1 is not prime at this web address:

    http://primes.utm.edu/notes/faq/one.html

    and I edited your code to include the following:

    Code:
     if(num == 1)
      {
    	  printf("The number %d is not prime due to special rules.\n", num);
      }
    
      else
      /* now test for factors */
    It seems to work well.

    Cheers

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You didn't need to test for 1, because they started their loop at 2.


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

  9. #9
    Registered User
    Join Date
    Feb 2005
    Posts
    19
    Testing for one is a true or false test. Yes, the loop must start at 2, because the of using the modulus
    operator. "is_prime = 1; " is merely an arbitrary starting point of a true or false condition.

    "for(i = 2;..." actual starts the test loop to check if the number is prime.

  10. #10
    @codeguru
    Join Date
    Jan 2006
    Posts
    34
    with prime you mean in power of 2? if so.

    Code:
    if((num & (num - 1)) != 0) printf("Number is not in power of 2!");

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple question regarding variables
    By Flakster in forum C++ Programming
    Replies: 10
    Last Post: 05-18-2005, 08:10 PM
  2. Simple class question
    By 99atlantic in forum C++ Programming
    Replies: 6
    Last Post: 04-20-2005, 11:41 PM
  3. Simple question about pausing program
    By Noid in forum C Programming
    Replies: 14
    Last Post: 04-02-2005, 09:46 AM
  4. simple question.
    By InvariantLoop in forum Windows Programming
    Replies: 4
    Last Post: 01-31-2005, 12:15 PM
  5. simple fgets question
    By theweirdo in forum C Programming
    Replies: 7
    Last Post: 01-27-2002, 06:58 PM