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

- 141.2K All Categories
- 104.5K Programming Languages
- 6.4K Assembler Developer
- 1.9K Basic
- 39.8K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 510 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 311 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 726 Computer Hardware
- 3.4K Database & SQL
- 522 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 256 XML Development
- 3.3K Classifieds
- 195 Co-operative Projects
- 182 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.2K Miscellaneous
- 3 Join the Team
- 0 User Profiles
- 349 Comments on this site
- 59 Computer Emulators
- 2K General programming
- 178 New programming languages
- 609 Off topic board
- 165 Mobile & Wireless
- 39 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 19 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 886 Software Development
- 405 Algorithms
- 68 Object Orientation
- 87 Project Management
- 90 Quality & Testing
- 235 Security
- 7.5K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 34 JQuery
- 287 WEB Servers
- 148 WEB-Services / SOAP

pascalstud10
Posts: **6**Member

in C and C++

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

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.

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

8Member1,625Membermy 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

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

6Member: 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

:

:

:

:

237Member: : [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

: :

: :

: :

: :

:

:

53MemberWow, 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.

3,711Member-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.

:

:

:

:

:

1,625Memberi'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

53MemberYeah, 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

67Member ✭Read here prime numbers