Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

display prime numbers

Posted on 2004-10-22
17
Medium Priority
?
424 Views
Last Modified: 2010-04-01
hi,
i need a program that displays the prime numbers.
range say 1-100.
Thanx
0
Comment
Question by:Mansoor Khan
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 5
  • 2
  • +3
17 Comments
 
LVL 3

Expert Comment

by:HendrikTYR
ID: 12387446
#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

by:HendrikTYR
ID: 12387467
... 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

by:Mansoor Khan
ID: 12388397
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 3

Expert Comment

by:HendrikTYR
ID: 12388488
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

by:bcsonka
ID: 12388758
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

by:
HendrikTYR earned 200 total points
ID: 12388806
..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

by:HendrikTYR
ID: 12388860
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

by:bcsonka
ID: 12388907
>> 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

by:Paladin_VB
ID: 12388940
BAAAH SMELLS LIKE HOMEWORK TO ME!
0
 
LVL 3

Expert Comment

by:HendrikTYR
ID: 12388945
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

by:zaghaghi
ID: 12390376
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

by:zaghaghi
ID: 12390425
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

by:zaghaghi
ID: 12390509
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

by:zaghaghi
ID: 12390550
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

by:HendrikTYR
ID: 12390589
Hi zaghaghi,

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

Expert Comment

by:zaghaghi
ID: 12390914
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

by:BenMorel
ID: 12391042
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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question