• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 426
  • Last Modified:

display prime numbers

hi,
i need a program that displays the prime numbers.
range say 1-100.
Thanx
0
Mansoor Khan
Asked:
Mansoor Khan
  • 7
  • 5
  • 2
  • +3
1 Solution
 
HendrikTYRCommented:
#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
 
HendrikTYRCommented:
... 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
 
Mansoor KhanCITAuthor 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
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
HendrikTYRCommented:
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
 
bcsonkaCommented:
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
 
HendrikTYRCommented:
..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
 
HendrikTYRCommented:
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
 
bcsonkaCommented:
>> 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
 
Paladin_VBCommented:
BAAAH SMELLS LIKE HOMEWORK TO ME!
0
 
HendrikTYRCommented:
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
 
Hamed ZaghaghiProgrammerCommented:
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
 
Hamed ZaghaghiProgrammerCommented:
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
 
Hamed ZaghaghiProgrammerCommented:
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
 
Hamed ZaghaghiProgrammerCommented:
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
 
HendrikTYRCommented:
Hi zaghaghi,

Just check, your first algorithm validtaes 1 as a prime number, ant it is not.
0
 
Hamed ZaghaghiProgrammerCommented:
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
 
BenMorelCommented:
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

The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

  • 7
  • 5
  • 2
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now