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

- 140.8K All Categories
- 104.4K Programming Languages
- 6.4K Assembler Developer
- 1.8K Basic
- 39.7K C and C++
- 4.2K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 1.9K PHP
- 506 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 310 Console programming
- 88 DirectX Game dev
- 1 Minecraft
- 109 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 726 Computer Hardware
- 3.4K Database & SQL
- 521 Electronics development
- 1.6K Matlab
- 627 Sound & Music
- 254 XML Development
- 3.3K Classifieds
- 190 Co-operative Projects
- 179 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
- 3K Miscellaneous
- 3 Join the Team
- 2 User Profiles
- 353 Comments on this site
- 60 Computer Emulators
- 1.8K General programming
- 178 New programming languages
- 603 Off topic board
- 166 Mobile & Wireless
- 40 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 17 Cloud Computing
- 52 FreeBSD
- 1.7K LINUX programming
- 366 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 887 Software Development
- 405 Algorithms
- 67 Object Orientation
- 85 Project Management
- 88 Quality & Testing
- 234 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
- 33 JQuery
- 285 WEB Servers
- 114 WEB-Services / SOAP

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.

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.

About & Contact / 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-2013 Programmersheaven.com - All rights reserved.

## Comments

8Member- Spam

0 · Vote Down Vote Up · Share on Facebook1,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

- Spam

0 · Vote Down Vote Up · Share on Facebook6Member: 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.

- Spam

0 · Vote Down Vote Up · Share on Facebook6Member: 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

:

:

:

:

- Spam

0 · Vote Down Vote Up · Share on Facebook237Member: : [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

: :

: :

: :

: :

:

:

- Spam

0 · Vote Down Vote Up · Share on Facebook53MemberWow, 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.

- Spam

0 · Vote Down Vote Up · Share on Facebook3,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.

:

:

:

:

:

- Spam

0 · Vote Down Vote Up · Share on Facebook1,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

- Spam

0 · Vote Down Vote Up · Share on Facebook53MemberYeah, 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

- Spam

0 · Vote Down Vote Up · Share on Facebook67Member ✭Read here prime numbers

- Spam

0 · Vote Down Vote Up · Share on Facebook