Help with prime number function, code included - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Help with prime number function, code included

[b][red]This message was edited by pascalstud10 at 2004-2-29 9:51:17[/red][/b][hr]
I am doing a program using microsoft visual c++ and need to come up with a function that will tell me if a number is prime or not. Ive got it about halfway figured out and any useful info on how to do this would be greatly appreciated. I will include what I have, I am stuck as the exact calculation of the prime:
#include

using std::cout;
using std::endl;

int prime( int ); //prime number function prototype

int main()
{
for (int x=2; x<=10000; x++)
cout<<"The Prime Numbers Between 2 and 10,000 are: "
<<prime(x)<<" ";
cout<<endl;

return 0;

} // end main function

//y is parameter
int prime( int y )
{ //not complete, just the beginning of function, not sure how to
//put it all together to run from 2-10000
if (y%x!=0)
return y;
} //end prime function


I am trying to figure out how to declare x as the value in the main fucntion or somehow simulate it as it will work. I thank you for your help.



Comments

  • roytangroytang Posts: 8Member
    Your prime() function makes no sense. What are you expecting it to do? Does it check if the passed value is a prime number? Or are you expecting it to return the yth prime number?
  • DarQDarQ Posts: 1,625Member
    [b][red]This message was edited by DarQ at 2004-2-29 7:26:56[/red][/b][hr]
    my first C function ;)

    [code]
    int is_prime(unsigned long i) {
    unsigned long k;

    for(k = 2; k < (i / 2) + 1; k++) {
    if(i % k == 0) {
    return 0;
    }
    }

    return 1;
    }
    [/code]


    : I am doing a program using microsoft visual c++ and need to come up with a function that will tell me if a number is prime or not. Ive got it about halfway figured out and any useful info on how to do this would be greatly appreciated. I will include what I have, I am stuck as the exact calculation of the prime:
    : #include
    :
    : using std::cout;
    : using std::endl;
    :
    : int prime( int ); //prime number function prototype
    :
    : int main()
    : {
    : for (int x=2; x<=10000; x++)
    : cout<<"The Prime Numbers Between 2 and 10,000 are: "
    : <<prime(x)<<" ";
    : cout<<endl;
    :
    : return 0;
    :
    : } // end main function
    :
    : //y is parameter
    : int prime( int y )
    : {
    : if (y%x!=0)
    : return y;
    : } //end prime function
    :
    :
    : I am trying to figure out how to declare x as the value in the main fucntion or somehow simulate it as it will work. I thank you for your help.
    :
    :

    [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    NEW url--> http://mark.space.servehttp.com



  • pascalstud10pascalstud10 Posts: 6Member
    [b][red]This message was edited by pascalstud10 at 2004-2-29 9:50:31[/red][/b][hr]
    : Your prime() function makes no sense. What are you expecting it to do? Does it check if the passed value is a prime number? Or are you expecting it to return the yth prime number?
    :
    To answer your question, it is not done yet. Its just like sorta somehow i thought of doing it but need it to check if there is a prime. And if so, to return that. So I want to have it run through every number from 2-10000 and output all the primes.


  • pascalstud10pascalstud10 Posts: 6Member
    : [b][red]This message was edited by DarQ at 2004-2-29 7:26:56[/red][/b][hr]
    : my first C function ;)
    :
    : [code]
    : int is_prime(unsigned long i) {
    : unsigned long k;
    :
    : for(k = 2; k < (i / 2) + 1; k++) {
    : if(i % k == 0) {
    : return 0;
    : }
    : }
    :
    : return 1;
    : }
    : [/code]

    DarQ could you explain your code some, im having some trouble following it.
    :
    :
    : : I am doing a program using microsoft visual c++ and need to come up with a function that will tell me if a number is prime or not. Ive got it about halfway figured out and any useful info on how to do this would be greatly appreciated. I will include what I have, I am stuck as the exact calculation of the prime:
    : : #include
    : :
    : : using std::cout;
    : : using std::endl;
    : :
    : : int prime( int ); //prime number function prototype
    : :
    : : int main()
    : : {
    : : for (int x=2; x<=10000; x++)
    : : cout<<"The Prime Numbers Between 2 and 10,000 are: "
    : : <<prime(x)<<" ";
    : : cout<<endl;
    : :
    : : return 0;
    : :
    : : } // end main function
    : :
    : : //y is parameter
    : : int prime( int y )
    : : {
    : : if (y%x!=0)
    : : return y;
    : : } //end prime function
    : :
    : :
    : : I am trying to figure out how to declare x as the value in the main fucntion or somehow simulate it as it will work. I thank you for your help.
    : :
    : :
    :
    : [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    : NEW url--> http://mark.space.servehttp.com
    :
    :
    :
    :

  • brtkltbrtklt Posts: 237Member
    In case you didn't know before the c99 standard, there was no boolean type so 1 and 0 were used as true and false respectively. What he's doing is passing an unsigned long to the function. Then in the for loop he starts the count at 2 since anythng is divisible by 1. The condition of the loop is ( k < (i / 2) + 1 ). Say you're dealing with a prime number and not a non-prime, the condition just avoids excessive looping since once you've gone past the value of (i / 2) + 1 the number is obviously prime and a 1 will be returned to indicate it's a value of true. If i % k returns 0 (meaning there is no remainder in the division) the number is obviously divisible by another number and is not prime so 0 is returned indicating a false value.

    : : [b][red]This message was edited by DarQ at 2004-2-29 7:26:56[/red][/b][hr]
    : : my first C function ;)
    : :
    : : [code]
    : : int is_prime(unsigned long i) {
    : : unsigned long k;
    : :
    : : for(k = 2; k < (i / 2) + 1; k++) {
    : : if(i % k == 0) {
    : : return 0;
    : : }
    : : }
    : :
    : : return 1;
    : : }
    : : [/code]
    :
    : DarQ could you explain your code some, im having some trouble following it.
    : :
    : :
    : : : I am doing a program using microsoft visual c++ and need to come up with a function that will tell me if a number is prime or not. Ive got it about halfway figured out and any useful info on how to do this would be greatly appreciated. I will include what I have, I am stuck as the exact calculation of the prime:
    : : : #include
    : : :
    : : : using std::cout;
    : : : using std::endl;
    : : :
    : : : int prime( int ); //prime number function prototype
    : : :
    : : : int main()
    : : : {
    : : : for (int x=2; x<=10000; x++)
    : : : cout<<"The Prime Numbers Between 2 and 10,000 are: "
    : : : <<prime(x)<<" ";
    : : : cout<<endl;
    : : :
    : : : return 0;
    : : :
    : : : } // end main function
    : : :
    : : : //y is parameter
    : : : int prime( int y )
    : : : {
    : : : if (y%x!=0)
    : : : return y;
    : : : } //end prime function
    : : :
    : : :
    : : : I am trying to figure out how to declare x as the value in the main fucntion or somehow simulate it as it will work. I thank you for your help.
    : : :
    : : :
    : :
    : : [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    : : NEW url--> http://mark.space.servehttp.com
    : :
    : :
    : :
    : :
    :
    :

  • SpookySpooky Posts: 53Member
    [b][red]This message was edited by Spooky at 2004-3-1 1:26:0[/red][/b][hr]
    Wow, your explanation is rally good.
    But in one point you both are wrong. You don't need to check the numbers from 2 to (i/2)+1. It's enough to check from 0 to sqrt(i). [red] - My bad, from 2 to sqrt(i). Sorry.[/red]
    Let's try it on the example of 100. It's not a prime number, but you can find all the numbers it can be divided with in the range from 2 to sqrt(100)=10. Let's see:
    100/2=50 100%2=0 - [blue]2,50[/blue]
    100/3=33 100%3=1
    100/4=25 100%4=0 - [blue]4,25[/blue]
    100/5=20 100%5=0 - [blue]5,20[/blue]
    100/6=16 100%6=4
    100/7=14 100%7=2
    100/8=12 100%8=4
    100/9=11 100%9=1
    100/10=10 100%10=0 - [blue]10[/blue]
    (The blue numbers on the right are the found numbers, that divide 100)

    That are all the operations you need to do to find all the numbers that divide a certain number. You may do yourself the same thing for 120 (11*11-1=121-1) to see, that you don't even need to go to sqrt(i)+1. But that's just one more iteration, so you can do it without a significant waste of computation time. But compared to range 0 - (i/2)+1 it is a significant difference. If you want to check 1 000 000 if it is a prime number, you can reduce the number of opration by:
    500001 - 1000 = 499001 operations, or
    500001 / 1000 = 500.001 times.
    I hope, you believe me now, that all dividers of a certain number (i) can be found in range 2 - sqrt(i). And if you find no divider in this range - there is no divider in the range 2 - (i/2)+1 and even in the range 2 - i => the number is prime.

    Spooky

    : In case you didn't know before the c99 standard, there was no boolean type so 1 and 0 were used as true and false respectively. What he's doing is passing an unsigned long to the function. Then in the for loop he starts the count at 2 since anythng is divisible by 1. The condition of the loop is ( k < (i / 2) + 1 ). Say you're dealing with a prime number and not a non-prime, the condition just avoids excessive looping since once you've gone past the value of (i / 2) + 1 the number is obviously prime and a 1 will be returned to indicate it's a value of true. If i % k returns 0 (meaning there is no remainder in the division) the number is obviously divisible by another number and is not prime so 0 is returned indicating a false value.




  • LundinLundin Posts: 3,711Member
    When making a prime number algo, then:
    -Don't divide by 1
    -Check if divisible by 2
    -Check if divisible by odd numbers, starting at 3

    If the number isn't divisible by 2, it is not divisible by 4 either!
    You will get twice as fast code when you don't check even numbers.



    : [b][red]This message was edited by Spooky at 2004-3-1 1:26:0[/red][/b][hr]
    : Wow, your explanation is rally good.
    : But in one point you both are wrong. You don't need to check the numbers from 2 to (i/2)+1. It's enough to check from 0 to sqrt(i). [red] - My bad, from 2 to sqrt(i). Sorry.[/red]
    : Let's try it on the example of 100. It's not a prime number, but you can find all the numbers it can be divided with in the range from 2 to sqrt(100)=10. Let's see:
    : 100/2=50 100%2=0 - [blue]2,50[/blue]
    : 100/3=33 100%3=1
    : 100/4=25 100%4=0 - [blue]4,25[/blue]
    : 100/5=20 100%5=0 - [blue]5,20[/blue]
    : 100/6=16 100%6=4
    : 100/7=14 100%7=2
    : 100/8=12 100%8=4
    : 100/9=11 100%9=1
    : 100/10=10 100%10=0 - [blue]10[/blue]
    : (The blue numbers on the right are the found numbers, that divide 100)
    :
    : That are all the operations you need to do to find all the numbers that divide a certain number. You may do yourself the same thing for 120 (11*11-1=121-1) to see, that you don't even need to go to sqrt(i)+1. But that's just one more iteration, so you can do it without a significant waste of computation time. But compared to range 0 - (i/2)+1 it is a significant difference. If you want to check 1 000 000 if it is a prime number, you can reduce the number of opration by:
    : 500001 - 1000 = 499001 operations, or
    : 500001 / 1000 = 500.001 times.
    : I hope, you believe me now, that all dividers of a certain number (i) can be found in range 2 - sqrt(i). And if you find no divider in this range - there is no divider in the range 2 - (i/2)+1 and even in the range 2 - i => the number is prime.
    :
    : Spooky
    :
    : : In case you didn't know before the c99 standard, there was no boolean type so 1 and 0 were used as true and false respectively. What he's doing is passing an unsigned long to the function. Then in the for loop he starts the count at 2 since anythng is divisible by 1. The condition of the loop is ( k < (i / 2) + 1 ). Say you're dealing with a prime number and not a non-prime, the condition just avoids excessive looping since once you've gone past the value of (i / 2) + 1 the number is obviously prime and a 1 will be returned to indicate it's a value of true. If i % k returns 0 (meaning there is no remainder in the division) the number is obviously divisible by another number and is not prime so 0 is returned indicating a false value.
    :
    :
    :
    :
    :

  • DarQDarQ Posts: 1,625Member
    hey,

    i've rarely seen someone describe such a piece of code with this excellence. I must totally agree with you. oh, i've written it myself.

    anyway, this is not such a neat piece of code. with big numbers with 8 digits orso, the function becomes awfully slow. The funny thing i found out when experimenting with the function that if N is a prime number, the loop will go until the end (obvious). but if N is not a prime, the loop ends really fast relative to (big number) N (which would be a prime).
    I here divide with 2, this is the lowest number you can divide with. With this particular number i started to mess after i found the loop is too slow. I multiplied 2 with 2 and started dividing with 4 DUH. but this could result in confirming that a number is a prime which is actually not. a bad solution.
    So i started again, but this time i would first divide by 2 and then with 4, 8, 16 and so on. By beginning with 2, i had always a correct prime or non-prime. Then doing the same number with 4, 8 etc and seeing if those divisions were correct according to division by 2.
    I saw that the bigger the number (N) which you want to see if its a prime, the bigger the division can be, thus making the loop much faster.

    PROBLEM: the size of N doesn't seem to relate to the division number. and here is where i got stuck. Anyone got an idea about this?
    maybe i was doing a complete bad approach, who knows.

    my complete C file
    arguments:
    1 begin N
    2 end N
    3 division (should use 2 for this)

    [code]
    #include
    #include

    int is_prime(unsigned long i, int div) {
    unsigned long k;

    for(k = 2; k < (i / div) + 1; k++) {
    if(i % k == 0) {
    return 0;
    }
    }

    return 1;
    }

    void test(unsigned long i, int div) {
    int prime;
    static int failures = 0;

    if (prime = is_prime(i, div)) {
    printf("index: %u == PRIMEnumber
    ", i);
    } else {
    printf("index: %u != PRIMEnumber
    ", i);
    }

    for (div; div < 65536; div *= 2) {
    if (is_prime(i, div) == prime) {
    printf(" division: %d --> passed
    ", div, i);
    } else {
    failures++;
    printf(" division: %d --> failed (failure: %d)
    ", div, i, failures);
    }
    }
    }

    void findprimes(unsigned long lower, unsigned long upper, int div) {
    unsigned long i;
    long begin;

    printf("Searching for primenumbers between %u and %u.
    ", lower, upper);

    for(i = lower; i < upper + 1; i += 2) {

    if (is_prime(i, div)) {
    printf("%u == PRIMEnumber
    ", i);
    }

    test(i, div);
    }
    }

    int main(int argc, char **argv) {
    int div;
    unsigned long lower, upper;

    printf("XPrime v0.1 (eXtended Prime-number Generator)
    ");
    printf("Floppyright 2004 by Mark Jelsma
    ");

    // If enough arguments are given, process
    if (argc == 4) {
    // Convert arguments to integers
    lower = atol((char *)argv[1]);
    upper = atol((char *)argv[2]);
    div = atoi((char *)argv[3]);

    // If lower/upper are even, make them odd and display a warning
    if (lower % 2 == 0) {
    printf("
    WARNING: Lower is not an odd value");

    lower++;
    }
    if (upper % 2 == 0) {
    printf("
    WARNING: Upper is not an odd value");

    upper++;
    }

    // Upper may not be smaller than lower
    if (upper <= lower) {
    printf("
    WARNING: Upper must not be smaller than lower");
    upper = lower + 100;
    }

    printf("

    ");

    findprimes(lower, upper, div);

    printf("a");

    return 1;
    } else {
    printf("
    ERROR: Too few arguments given...
    ");

    return 0;
    }
    }
    [/code]

    : In case you didn't know before the c99 standard, there was no boolean type so 1 and 0 were used as true and false respectively. What he's doing is passing an unsigned long to the function. Then in the for loop he starts the count at 2 since anythng is divisible by 1. The condition of the loop is ( k < (i / 2) + 1 ). Say you're dealing with a prime number and not a non-prime, the condition just avoids excessive looping since once you've gone past the value of (i / 2) + 1 the number is obviously prime and a 1 will be returned to indicate it's a value of true. If i % k returns 0 (meaning there is no remainder in the division) the number is obviously divisible by another number and is not prime so 0 is returned indicating a false value.
    :
    : : : [b][red]This message was edited by DarQ at 2004-2-29 7:26:56[/red][/b][hr]
    : : : my first C function ;)
    : : :
    : : : [code]
    : : : int is_prime(unsigned long i) {
    : : : unsigned long k;
    : : :
    : : : for(k = 2; k < (i / 2) + 1; k++) {
    : : : if(i % k == 0) {
    : : : return 0;
    : : : }
    : : : }
    : : :
    : : : return 1;
    : : : }
    : : : [/code]
    : :
    : : DarQ could you explain your code some, im having some trouble following it.
    : : :
    : : :
    : : : : I am doing a program using microsoft visual c++ and need to come up with a function that will tell me if a number is prime or not. Ive got it about halfway figured out and any useful info on how to do this would be greatly appreciated. I will include what I have, I am stuck as the exact calculation of the prime:
    : : : : #include <iostream>
    : : : :
    : : : : using std::cout;
    : : : : using std::endl;
    : : : :
    : : : : int prime( int ); //prime number function prototype
    : : : :
    : : : : int main()
    : : : : {
    : : : : for (int x=2; x<=10000; x++)
    : : : : cout<<"The Prime Numbers Between 2 and 10,000 are: "
    : : : : <<prime(x)<<" ";
    : : : : cout<<endl;
    : : : :
    : : : : return 0;
    : : : :
    : : : : } // end main function
    : : : :
    : : : : //y is parameter
    : : : : int prime( int y )
    : : : : {
    : : : : if (y%x!=0)
    : : : : return y;
    : : : : } //end prime function
    : : : :
    : : : :
    : : : : I am trying to figure out how to declare x as the value in the main fucntion or somehow simulate it as it will work. I thank you for your help.
    : : : :
    : : : :
    : : :
    : : : [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    : : : NEW url--> http://mark.space.servehttp.com
    : : :
    : : :
    : : :
    : : :
    : :
    : :
    :
    :

    [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    NEW url--> http://mark.space.servehttp.com

  • SpookySpooky Posts: 53Member
    : maybe i was doing a complete bad approach, who knows.

    Yeah, that's right. In my previous post on this topic I explained, why is it sufficient to test the range from 2 to sqrt(i).
    Lundin in his reply pointed out, that it's of no use to test the even numbers if you just want to test if a number is prime. So here is the modified is_prime function:

    [code]
    //Check if a number is prime
    //Parameters:
    // n - number to check
    //Return value:
    // 0 - not a prime number
    // 1 - prime number
    int is_prime(unsigned long n)
    {
    unsigned long i,end;

    if(n%2 == 0)
    {
    return 0;
    }

    end=(unsigned long)sqrt(n);

    for(i=3;i<=end;i+=2)
    {
    if(n%i==0)
    {
    return 0;
    }
    }

    //it is a prime number
    return 1;
    }
    [/code]

    This should be a pretty fast method. Even if testing if 1 000 000 is a prime number, this function does max. 500 loops + 1 check at the beginning, so it's 501 operations instead of your 500 000 when dividing by 2.

    Spooky
  • globalprogglobalprog Posts: 67Member
Sign In or Register to comment.