Solved

display prime numbers

Posted on 2004-10-22
385 Views
Last Modified: 2010-04-01
hi,
i need a program that displays the prime numbers.
range say 1-100.
Thanx
0
Question by:mak47pk
    17 Comments
     
    LVL 3

    Expert Comment

    by:HendrikTYR
    #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
    ... 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:mak47pk
    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

    by:HendrikTYR
    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
    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:
    ..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
    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
    >> 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
    BAAAH SMELLS LIKE HOMEWORK TO ME!
    0
     
    LVL 3

    Expert Comment

    by:HendrikTYR
    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
    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
    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
    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
    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
    Hi zaghaghi,

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

    Expert Comment

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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    What Security Threats Are You Missing?

    Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

    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++.

    875 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

    Need Help in Real-Time?

    Connect with top rated Experts

    15 Experts available now in Live!

    Get 1:1 Help Now