# display prime numbers

hi,
i need a program that displays the prime numbers.
range say 1-100.
Thanx
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
#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
Commented:
... 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
CITAuthor Commented:
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
Commented:
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
Commented:
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
Commented:
..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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
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
Commented:
>> 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
Commented:
BAAAH SMELLS LIKE HOMEWORK TO ME!
0
Commented:
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
ProgrammerCommented:
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
ProgrammerCommented:
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
ProgrammerCommented:
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
ProgrammerCommented:
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
Commented:
Hi zaghaghi,

Just check, your first algorithm validtaes 1 as a prime number, ant it is not.
0
ProgrammerCommented:
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
Commented:
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
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.