about counting prime numbers

This is a discussion on about counting prime numbers within the C++ Programming forums, part of the General Programming Boards category; #include <iostream> using namespace std; int main(void) { cout << "Input the largest positive integer to check: "; unsigned int ...

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    2

    about counting prime numbers

    #include <iostream>
    using namespace std;
    int main(void)

    {
    cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;

    unsigned int nPrimes =0;

    for (int i = 2; i <=maxN; i =i + 1)
    {
    bool isPrime =true;
    for (int j =2; j < i; j =j + 1)
    {
    if (i%j ==0) isPrime =false;
    }
    if (isPrime)
    { // cout << i << " "; //Use to check that you’re getting primes

    nPrimes =nPrimes + 1;
    }
    }
    cout << "\n\nThere are " << nPrimes << " prime numbers <=" << maxN << endl;

    return 0;
    Code:
    #include <iostream>

  2. #2
    Registered User
    Join Date
    Oct 2003
    Posts
    2

    the code above

    Hi,
    I'm pretty new with c++ and have a question about coding a program that counts the prime numbers in a range of 2 to 100000. Actually I have a code written above but it counts the prime numbers very slowly. It takes about 130 seconds for the program to count the prime numbers up to 100000. How can I make it faster? Should I use vectors? I should get this code working about more than 5000 times faster. I appreciate your help, thanks....

  3. #3
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    You do not need to test the number N until N-1. I mean, the square of the number is a good limit:
    Code:
    int main()
    {
       for(int i=1;i<100000;i++)
       {
          bool prime = true;
          if( i%2!=0){
             float limit = sqrt(i);
             for(j=3;j<limit && prime;j+=2){
                if( i%j==0 ) prime = false;
             }
          }
          else prime = false;
          if( prime ) cout << i << "is prime" << endl;
    }
    Last edited by gustavosserra; 10-28-2003 at 07:51 AM.
    Nothing more to tell about me...
    Happy day =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  2. Counting Numbers in Array, not counting last number!
    By metaljester in forum C++ Programming
    Replies: 11
    Last Post: 10-18-2006, 11:25 AM
  3. prime numbers code compile error
    By Tony654321 in forum C Programming
    Replies: 5
    Last Post: 10-10-2004, 10:13 AM
  4. Replies: 2
    Last Post: 09-11-2002, 05:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21