Thread: prime number.

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    3

    prime number.

    ok im in this call for c programing. and the newest assignment is this.

    Write a program that inputs a number and determines whether the number is prime. After displaying the results, ask the user if they want to try again. At the end, print "Have a nice day!". Sample output:

    Enter number: 25
    The number 25 is not prime.
    Continue? (y/n) y
    Enter number: 17
    The number 17 is prime.
    Continue? (y/n) n
    Have a nice day!

    this assignment is really screwing me. i need help bad. if you could send me the program in the simplest terms possible so it looks like a beggining student could have written it i would be very greatful. thanks.

  2. #2
    Registered User kinghajj's Avatar
    Join Date
    Jun 2003
    Posts
    218
    I don't know how to test primes, so check google.

    Code:
    #include <stdio.h>
    
    int TestPrime(int n)
    {
     ... your code here ...
    }
    
    int main()
    {
        char continue = 'y';
        int number;
    
        while(continue == 'y')
        {
            printf("Enter Number: ");
            scanf("%i", &number);
            if(TestPrime(number))
            {
                printf("%i is prime\n", number);
            }
            else
            {
                printf("%i is not prime\n",number);
            }
            printf("Do you want to continue? [y/n] ");
            continue = getc();
        }
        return 0;
    }
    So, you just need to find out how to get TestPrime to work
    }
    01011001 01101111 01110101 00100000 01110100 01101111 01101111 1101011 00100000 01110100 01101000 01101001 01110011 00100000 01101101 01110101 01100011 01101000 00100000 01110100 01101000 01101101 01100101 00100000 01110100 01101111 00100000 01110010 01100101 01100001 01100100 00100000 01011001 01101000 01101001 01110011 00111111 00100000 01000100 01100001 01101101 01101110 00100001 00000000

  3. #3
    I like code Rouss's Avatar
    Join Date
    Apr 2004
    Posts
    131
    To test a number for primeness (??), just try looping through all the values between 2 and that number, and mod (%) the number in question by the loop variable... If it is equal to 0, then it can't be prime.

  4. #4
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    you would need 2 nested loops... your example won't work... take 9 for example, not prime, but your algorithm says it is because it never tests 3*3, only 2*9,3*9,4*9, etc.

    the first loop increments the first operand, and the inner loop increments the second.
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Code:
    int isdiv(int dividend, int divisor)
    {
      return (dividend % divisor) == 0;
    }
    
    int isprime(int num)
    {
      int i;
    
      i = 2;
      while (((i * i) < num) && (isdiv(num, i) == 0))
        ++i;
      if (i * i > num) return 1;
      else return 0;
    }
    Copied from http://www.drtak.org/teaches/ARC/cis.../proj3/prime.c
    That is a C code equivlent for an assembly homework we had to do. As such it really doesn't really need to be broken into two functions.

  6. #6
    Registered User
    Join Date
    May 2004
    Posts
    1
    If input_number is the input number,

    for( i = 0; i < input_number/2; i++)
    {
    if (( input_number % i) == 0)
    {
    printf( "not prime number ");
    break;
    flag = false;
    }
    }

    if ( flag != false)
    printf( "The number is prime");


    This the code for checking the prime number

  7. #7
    The Artful Lurker Deckard's Avatar
    Join Date
    Jan 2002
    Posts
    633
    I recently worked on a prime number generator here at work (I cannot share the code with you). I just wanted to point out that after you test the number against 3 (n % 3), you only need to test odd numbers after that. So, start at 2, go to 3, then increment by two each time after that. It will make your code much faster.

    Also, you only need to check odd numbers (besides 2) up to the square root of the number you're testing (not all the way up to the number itself).

    I hope that helps.
    Jason Deckard

  8. #8
    I like code Rouss's Avatar
    Join Date
    Apr 2004
    Posts
    131
    Quote Originally Posted by major_small
    you would need 2 nested loops... your example won't work... take 9 for example, not prime, but your algorithm says it is because it never tests 3*3, only 2*9,3*9,4*9, etc.

    the first loop increments the first operand, and the inner loop increments the second.
    I think you referring to my post.

    But I didn't say to multiply, I said to mod.
    So when it tested 9, the loop should go like this:
    Code:
    9 % 2 = 1
    9 % 3 = 0 (return some indication that it is not prime, 0 perhaps
    As for a prime such as 11, let's say. It would iterate through the entire loop, never having 11 % i (iterator) == 0, so when it exits the loop, just return 1 or some other indication that it is prime.

    I hope I was more clear this time. I think that what I have said works, if not, please let me know.

    Also, Deckard made some very good points. I would say test num % 2, before the loop, then start the loop at 3, and increment by 2... I guess sqrt() would be good to throw in there since it will make it faster.

    Rouss

  9. #9
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I would creat an array with the first 100 prime numbers then use a sieve method. Sieve of Eratosthenes

  10. #10
    Registered User
    Join Date
    Apr 2004
    Posts
    26
    I just want to point on this part of codes written by kinghajj char continue = 'y';

    continue is reserved keyword, so is it allowed for naming variables? I know so far that it is not allowed. Anyway kinghajj has good suggestion for this kind of problem.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No, it isn't allowed. That code will not compile for the reson you've stated.

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

  12. #12
    ---
    Join Date
    May 2004
    Posts
    1,379
    http://mathworld.wolfram.com/PrimeNumber.html

    formulae for prime numbers. with the exception of 2 and 3 but you can manually check for that.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    So far it looks like you're just going to use trial division, and it'll be on fairly small primes.

    The fastest testing when using trial division is when only prime numbers up to the square root of the given integer is used to test.

    So a simple idea is to calculate (or pre-calculate) an array of primes, then test from 2 to the last prime in that array, or stop when the integer is shown to be composite.
    If the test number is within the range of this array, you could also use say, binary search instead of trial division, i.e. not found means composite.

    There is a little bit of cheating that might be involved though, since it would be advantageous to at least pre-calculate the size of the array, if you dont want to pre-calculate the whole array.
    The array itself could be obtained easily by using a sieve such as the Sieve of Eratosthenes, as mentioned earlier.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User caroundw5h's Avatar
    Join Date
    Oct 2003
    Posts
    751
    I recently did submitted some code about primes here . it was a more efficent method of finding primes. saved a lot of time. You can see the basic idea in the code and then add kinghaji if/else clause to terminate or continue the program.
    Good luck.
    Warning: Opinions subject to change without notice

    The C Library Reference Guide
    Understand the fundamentals
    Then have some more fun

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. largest number prime number that can be produced...
    By ElemenT.usha in forum C Programming
    Replies: 8
    Last Post: 02-17-2008, 01:44 AM
  3. Prime Factor Fxn
    By alpha in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 10:44 AM
  4. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  5. Replies: 3
    Last Post: 01-14-2003, 10:34 PM