# 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.

• 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?
• [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

• [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.

• : [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
:
:
:
:

• 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
: :
: :
: :
: :
:
:

• [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.

• 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.
:
:
:
:
:

• 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)) {
", i);
} else {
", 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)) {
", 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

• : 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