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

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# Help with prime number function, code included

Posts: 6Member
[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.

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

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

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

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

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

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

• 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)) {
", 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

• 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
• Posts: 67Member