Solved

# display prime numbers

Posted on 2004-10-22
385 Views
hi,
i need a program that displays the prime numbers.
range say 1-100.
Thanx
0
Question by:mak47pk

LVL 3

Expert Comment

#include <iostream>
#include <conio.h>
using namespace std;

bool isPrime(int nr) {
bool ret = (nr > 1);
int div = nr - 1;
while(ret && (div > 1)) ret = nr % div--;
return ret;
}

int main() {
int n = 100;
int nr = 1;
while(n) {
if(isPrime(nr)) {
cout << nr << endl;
n--;
}
nr++;
}

getch();
return 0;
}

Regards,
Hendrik
0

LVL 3

Expert Comment

... or somewhat better when getting to bigger numbers:

bool isPrime(int nr) {
bool ret = (nr > 1);
int div = 2;
while(ret && (div*div < nr)) ret = nr % div++;
return ret;
}
0

Author Comment

hi Hendrik,
this function is not working properly;

bool isPrime(int nr) {
bool ret = (nr > 1);
int div = nr - 1;
while(ret && (div > 1)) ret = nr % div--;
return ret;
}

please also explan the working of while loop.
thanx.
0

LVL 3

Expert Comment

Hi,

If you set n = 100 you will get the first 100 prime numbers.
If with "Range 1-100" you meant you wanted all prime numbers smaller than 100, then just change main() to:

int main() {
int nr = 1;
while(nr <= 100) {
if(isPrime(nr)) cout << nr << endl;
nr++;
}

getch();
return 0;
}

Explanation for: while(ret && (div > 1)) ret = nr % div--;
(...and by the way, it works fine for me :)
1. ret is set to true to begin with (remember 1 is not a prime number)
2. if your number is divisible by any number other than itself or 1, then it is NOT prime, so if the loop finds a number that is a factor of the number being tested the loop will quit and false will be returned.
3. So we start with the first number lower than our number being tested: div = nr-1;
and we decrease div until it reaches 1

The second "isPrime(int nr)" function I posted is slightly better, since it will start testing at a much smaller number than (nr-1).  We may do this because there is no other factor for a number bigger than its square root :)
0

LVL 2

Expert Comment

Hi,

Here's another way to determine if a number is prime.  The code is longer but still works.

============================================================================

bool IsPrime(const int number)
{
bool isPrime = false;

if(number <= 1)  // A prime number is defined as a whole number greater than 1
{
isPrime = false;
}
else if(number == 2 || number == 5)  // 2 and 5 are prime numbers
{
isPrime = true;
}
else
{
// Change the size of this character array for your own purposes.
// I'm just being paranoid in this example.
char numberAsString[32];
char lastDigitInNumber;

// Convert number to a string
itoa(number, numberAsString, 10);

// Determine the last digit in number
lastDigitInNumber = numberAsString[strlen(numberAsString) - 1];

// When we get to this point, only numbers in which the last digit is 1, 3, 7, or 9 are prime numbers
if(lastDigitInNumber == '1' || lastDigitInNumber == '3' || lastDigitInNumber == '7' || lastDigitInNumber == '9')
{
// Determine half of the number passed as a parameter (drop the remainder)
int halfOfNumber = number / 2;

// Initialize isPrime to true before we enter the for loop
isPrime = true;

// Loop through each divisor from 2 to halfOfNumber
for(int divisor = 2; divisor <= halfOfNumber; divisor++)
{
// If you divide number by divisor and there is no remainder,
// then number is divisible by the divisor.
// Thus, number is not prime and we should break out of the loop.
if((number % divisor) == 0)
{
isPrime = false;
break;
}
}
}
}

return isPrime;
}

============================================================================

I hope that helps.
0

LVL 3

Accepted Solution

..oops, my apologies for the second algorithm I posted:

it should be:

bool isPrime(int nr) {
bool ret = (nr > 1);
int div = 2;
while(ret && (div*div <= nr)) ret = nr % div++;
return ret;
}

, ie.  did*div <= nr and not div*div < nr, otherwise I'm missing all the squares

The first algorithm is correct though.
0

LVL 3

Expert Comment

Hi bcsonka,

Just wondering why all the trouble to eliminate 1,2,5 and then all numbers not ending in 1,3,7,9
0

LVL 2

Expert Comment

>> Just wondering why all the trouble to eliminate 1,2,5 and then all numbers not ending in 1,3,7,9

I added that logic in for performance purposes.  The looping really only applies to the numbers ending in 1, 3, 7, and 9.  I figure eliminating the numbers that don't apply would save the trouble of going through the for loop.
0

LVL 1

Expert Comment

BAAAH SMELLS LIKE HOMEWORK TO ME!
0

LVL 3

Expert Comment

Thought so, but actually by using strings to do it, execution now takes significantly longer:

on my machine this algorithm:
bool isPrime(int nr) {
bool ret = (nr > 1);
int div = 2;
while(ret && (div*div <= nr)) ret = nr % div++;
return ret;
}

takes less than 1 second to get the first 10 000 prime numbers, yours take 7 seconds.

It can also get the first 100 000 prime numbers in 3 seconds, yours took several minutes.

My intention is really not to be critical, but I got the feeling that you were looking for performance, so give it a try.

It is really working now that I fixed the "<=" typo :)
0

LVL 9

Expert Comment

hi,

some of experts, use algorithms to find prime numbers, but!!
there is two common way to find a prime number:

1- for each number, test if there is a prime number that devides this number, the number is not a prime number, and else it is a prime number.

2- use a list for all numbers in the range, and then start from 2, and delete all numbers that are multiple of 2 from the list, and the next number that remind in the list is the next prime number, so like 2 remove all numbers that are multiple of the next prime number, and do this step 'til reach to the end of the list.

3- note , if your range is very large this algorithm work slowly, and the second algorithm give a lot of memory, but there are some primerlity testing that test if this number is complex or not, like Ferma theorem.

have a good prime finding,;)

0

LVL 9

Expert Comment

hi,

use this code, for example:

bool isPrime(int num)
{
int i;
if(num%2==0)
return false;
for(i=3; i*i<=num; i++)
if(num%i==0)
return false;
return true;
}

0

LVL 9

Expert Comment

for showing all primes in range 1-end:

#include "vector"

using namespace std;

vector<int>primes;

bool isPrime(int num)
{
int i;
int size = primes.size();
for(i=0; i<size; i++)
if(num%primes[i]==0)
return false;
return true;
}

void findPrimes(int end)
{
int i;
primes.push_back(2);
for(i=3; i<=end; i++)
if(isPrime(i))
primes.push_back(i);
}

0

LVL 9

Expert Comment

and the other algorithm with better time than previous algorithm:

#include "memory"
using namespace std;

#define MAX  100

bool allnumbers[MAX+1];

void setPrimes(int max)
{
int i,j;
memset(allnumbers, true, sizeof allnumbers);
allnumbers[0]=allnumbers[1]=false;
for(i=2; i<=max; i++){
if(allnumbers[i]){
for(j=2*i; j<=max; j+=i)
allnumbers[j]=false;
}
}
}

0

LVL 3

Expert Comment

Hi zaghaghi,

Just check, your first algorithm validtaes 1 as a prime number, ant it is not.
0

LVL 9

Expert Comment

hi & tnx HendrikTYR,

my first code must be:

bool isPrime(int num)
{
int i;
if(num<2) eturn false;
if(num%2==0)
return false;
for(i=3; i*i<=num; i+=2)
if(num%i==0)
return false;
return true;
}

;)
0

LVL 7

Expert Comment

Here is an optimized (and working ;-) code :

=========================
#include <stdio.h>

#define MAX 100

int main(void) {
register unsigned int i,j;
register bool isPrime;
if (MAX>0) printf("1\n");
if (MAX>1) printf("2\n");
for (i=3; i<MAX; i+=2) {
isPrime = true;
for (j=3; j*j<i; j+=2) {
if (i%j == 0) {
isPrime = false;
break;
}
}
if (isPrime) printf("%u\n", i);
}
return 0;
}
=========================

See ya
Ben
0

## Featured Post

Some Windows API functions expect you to provide a pointer to a CALLBACK function that the system will need to call as part of the operation.  Such API functions as SetTimer, timeSetEvent, CreateThread, EnumWindows, LineDDA, even window message handâ€¦
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. â€¦
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.