Not Yet Answered # isPrime()

Narue 5,707 Discussion Starter forumposters Narue 5,707 JRM 107 soeja soeja parameshyss hvengel StuXYZ 731 pseudorandom21 166 hvengel pseudorandom21 166 yashsaxena -1 Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

>I'm new to C++ and any help would be appreciated.

At least start trying to solve your problem before asking for help. It makes us like you more and ignore you less.

0

Here's what I've come up with so far:

```
#include <iostream>
bool IsPrime(int num)
{
if(num == 0)
return true;
num = abs(num);
for(int i = 2; i <= sqrt(num); i++)
if(num % i == 0)
return false;
return true;
}
```

0

>Here's what I've come up with so far

Somehow I find it hard to believe that you can write IsPrime but not the main driver to print the primes in the range [0..100). I'm guessing you were given IsPrime and told to write main, which means ** you've** come up with nothing so far. But, the hard part is done already. All you need to do is loop from 0 to 100 and call IsPrime on the current number. If it returns true, print the number:

```
for ( int i = 0; i < 100; i++ ) {
if ( IsPrime ( i ) )
cout<< i <<" is prime\n";
}
```

0

Here's what I've come up with so far

Somehow I find it hard to believe that you can write IsPrime but not the main driver to print the primes in the range [0..100). I'm guessing you were given IsPrime and told to write main, which meanscome up with nothing so far.you've

LOL! If some people would put half of the effort that they put into "avoiding work" into something productive, they would have had the task acomplished by now!

If laziness is truely the mother of invention, we have quite a group of potential inventors here!

*Edited 3 Years Ago by pyTony*: fixed formating

0

This is more efficient.

#include <iostream>

bool IsPrime(int num)

{

if(num == 0)

return true;

num = abs(num);

if(num % 2 == 0) return true;

for(int i = 3; i <= sqrt(num); i+=2)

if(num % i == 0)

return false;

return true;

}

-1

```
#include <iostream>
bool IsPrime(int num)
{
if(num == 0)
return true;
num = abs(num);
if(num % 2 == 0) return true;
for(int i = 3; i <= sqrt(num); i+=2)
if(num % i == 0)
return false;
return true;
}
```

-1

Hi Soeja,

This is more efficient.. and for 4 , 6 , 8(i.e., even no) .. ur code snippet will give wrong ans..

```
#include <iostream>
bool IsPrime (int num)
{
if ( 2 == num ) return true ;
int l = sqrt(num) ;
for(int i = 3; i <= l; i+=2)
if ( 0 == ( num % i ) )
return false;
return true;
}
```

*Edited 5 Years Ago by Ezzaral*: Snipped blog link. Please confine personal links to your user signature.

0

An even more efficient and generalized isPrime() function.

```
bool isPrime (unsigned int number)
{
if (number > 3) {
if (number % 2 == 0) return false;
const unsigned int MAX = (unsigned int)sqrt(number) + 1;
for (unsigned int i = 3; i < MAX; i += 2 )
if ( (number % i) == 0)
return false;
return true;
}
if (number < 2) return false;
return true;
}
```

0

I am surprised reading this, I would have thought most of you knew the +2,+4 rule --

but it hasn't come up, just the old +2 rule.

Assuming that you are not going to use the memory that the typical sieve methods use, or the complexity of the more you can extend the idea that you increment the test by +2 to +2,+4 as below.

```
bool isPrime2(unsigned int& number)
{
if (number > 3)
{
if (number % 2 == 0) return false;
if (number % 3 == 0) return false;
const int MAX = (int)sqrt(number) + 1;
int i=5;
while(i<MAX)
{
if ( (number % i) == 0) return false;
i+=2;
if ( (number % i) == 0) return false;
i+=4;
}
}
else if (number<2)
{
return false;
}
return true;
}
```

The code as given is about 45% quicker than the simple +2 system. However, there are many other ways of doing things.

The next obvious extension is sometimes called the wheel factorization , e.g. http://primes.utm.edu/ That reference has lots of other algorithms as well.

*Edited 5 Years Ago by StuXYZ*: n/a

0

I think a sieve that uses a bit of memory is way better than using that much CPU time, you can generate millions of primes in a few seconds using a sieve.

0

```
#include <math.h>
#include <vector>
using namespace std;
const int NUM_FIRST_PRIMES = 3;
const unsigned int FIRST_PRIMES[NUM_FIRST_PRIMES] = {2, 3, 5};
vector<unsigned int> sieve;
unsigned int wheelFactor = 1;
bool seiveFull = false;
void fillSieve() {
wheelFactor = 1;
for (int i=0; i < NUM_FIRST_PRIMES; i++)
wheelFactor = wheelFactor * FIRST_PRIMES[i];
unsigned int i = 0;
int sieveValue = FIRST_PRIMES[NUM_FIRST_PRIMES - 1] + 1;
while (sieveValue < wheelFactor){
bool factor = true;
for (int j=0; j < 8; j++)
if (sieveValue % FIRST_PRIMES[j] == 0) {
i++;
factor = false;
break;
}
if (factor) {
sieve.push_back(sieveValue);
}
sieveValue++;
}
sieve.push_back(wheelFactor + 1);
sieveFull = true;
}
bool isPrime (unsigned int candidatePrime)
{
if (!sieveFull) fillSieve();
int fp = 0;
while (fp < NUM_FIRST_PRIMES) {
if (candidatePrime == FIRST_PRIMES[fp]) return true;
if (candidatePrime % FIRST_PRIMES[fp] == 0 && candidatePrime > 3) return false;
fp++;
}
const unsigned int MAX = (unsigned int)sqrt(candidatePrime);
int pass = 0;
while (pass < MAX) {
int i = 0;
while (i < sieve.size()) {
if (candidatePrime == (pass + sieve[i])) return true;
if (candidatePrime % (pass + sieve[i]) == 0) return false;
i++;
}
pass += wheelFactor;
}
return true;
}
```

Here is a wheel factorization version of isPrime. This uses a small wheel factoring sieve based on the first three primes. When used to find the sum of all primes up to some limit it is slower than my earlier function up to finding the sum of all primes below 100,000 and faster for larger test cases. It is about 40% faster when finding all primes below 1,000,000 and about 45% faster when finding the first 20,000,000 primes. This is probably because of the extra overhead of building the sieve and perhaps some added overhead from using a vector to hold the sieve.

It should be possible to extent this to use a larger sieve by using a larger first primes set and this should make it run faster when testing larger values or when working with a larger set of data but it will be even slower when using it with smaller data sets because of the added initialization overhead which grow exponentially as the number of first primes get bigger.

I have not tested this code with a bigger sieve so it might needs some tweaks.

0

http://en.wikipedia.org/wiki/Primality_test

You might also look into the sieve of eratosthenes, and other algorithms for generating primes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

There are links to other algorithms at the bottom, such as the sieve of sundaram, etc.

0

prime number program :)

Still remember the initial days of C & CPP programming Language. :P :)

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...