Thread: Prime Number?

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    3

    Question Prime Number?

    Hi guys,
    I am pretty new to C and I need a little help. I am trying to write a program to determine a prime number for my class lab. I am a little confused to say the least and was wondering if anybody could help me. I just want an idea of how to get this thing going. Could someone break it down for me. I feel like a moron!!!

    Thanks,
    Joe

  2. #2
    Registered User heljy's Avatar
    Join Date
    Mar 2002
    Posts
    36
    Let me try...

    Firstly you have to know how you would determine a prime number logically, ie come out with an algorithmn, just a simple one that you would normally use to work out if using paper and pencil...

    I think the simplest is something like this (correct me if I am wrong):

    A number is prime if its not divisble by all the (positive) numbers before it (except 1 of course).

    With that you can start translating it to code. Of course the algorithmn is really inefficient, but the main thing would to get it to work first and then try to optimize it later...

    Hope that helps.

    Good luck
    If only life is as easy as C...

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    197
    Here is an efficient algorithm to find prime numbers.

    klausi
    When I close my eyes nobody can see me...

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    3

    Question

    ok I have a little code here. It doesnt work but I think I have the right I idea. It basically tells me that every # is not prime except for the # 1. Here goes nothing:

    Its a function and the prime is being passed in:

    char test_prime(int prime)

    {

    int r; /* the remainder*/
    int i; /*the numbers up to the prime*/

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

    r = prime % i;
    /*basically what i want it to do is take all of the numbers greater than 2 and up to the prime and mod them. If the remainder is equal to zero then it will not be prime, right? */

    if(r == 0)
    {
    return('n'); /*not prime*/
    }
    else
    {
    return('p'); /*prime*/
    }

    }

    Thanks guys,
    Joe

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    197
    I didnīt compile it, but it should work.
    You can make it more efficient if you write
    Code:
    for(i=2; i<sqrt(prime)+1;i++)
    I donīt know if the name for the function to get a square-root is really "sqrt", but I think so.
    You have to include <math.h> into your code, to use the sqrt() function.

    klausi
    When I close my eyes nobody can see me...

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    197
    Your code doesnīt work, but I know that it has been corrected by another one.
    klausi
    When I close my eyes nobody can see me...

  7. #7
    Registered User heljy's Avatar
    Join Date
    Mar 2002
    Posts
    36
    Hmm...actually

    Try this

    // first check if number is even; if so not prime
    if(!prime%2)
    r = 1;

    // then check every odd number
    for(i=3; i<sqrt(prime) + 1 && !r; i+=2)
    if(prime%i)
    r = 1;

    You only check if the number is odd, so I guess it more efficient.

    Of course you have to check the speical case when:

    prime == 2
    If only life is as easy as C...

  8. #8
    Unregistered
    Guest
    Your code does not work

    [code]
    char test_prime(int prime)
    {
    int r; /* the remainder*/
    int i; /*the numbers up to the prime*/

    for(i=2; i<prime;i++)
    r = prime % i;
    if(r == 0)
    {
    return('n'); /*not prime*/
    }
    else
    {
    prime could still not be prime here, 15 is not
    divisible by 2 but is not prime.
    return('p'); /*prime*/
    }
    }

    Also remember that 1 is not prime.

  9. #9
    Registered User
    Join Date
    Mar 2002
    Posts
    1

    Cool

    Try this:

    #include <stdio.h>

    main(){
    int primetested,numberofprimes, primesfound, x;

    printf("Enter the number primes you want: ");
    scanf ("%d", &numberofprimes);

    printf("1 is prime\n");

    primesfound = 1;
    primetested = 3;

    while (primesfound < numberofprimes){
    x = 2;

    while (primetested > x){

    if (x != primetested && primetested % x == 0){
    break;
    }
    x++;
    }

    if (x == primetested){
    printf("%d is prime\n", primetested);
    primesfound++;
    }
    ++primetested;
    }

    return 0;
    }

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