LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 10-20-2005, 07:39 PM   #1
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Rep: Reputation: 15
increase code speed


I was given this code:
Code:
#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 << " ";
                nPrimes = nPrimes + 1;
            }
    }
    cout << "\n\nThere are " << nPrimes << " prime numbers <= " << maxN << "\n";
    return 0;
}
My assignment is to make this code go faster and find the number of prime numbers smaller than a given integer. I'm not asking for the answer! I would just like a hint if anyone knows what I should do. I know I need to use vectors and our professor told us a hint that if you cancel all of the multiples of the prime numbers below the square root of the maximum number, the rest are primes, but I don't know how to put that into my code. Any hints for me??
 
Old 10-20-2005, 07:45 PM   #2
rshaw
Senior Member
 
Registered: Apr 2001
Location: Perry, Iowa
Distribution: Mepis , Debian
Posts: 2,694

Rep: Reputation: 45
google for 'sieve of Eratosthenes'
 
Old 10-20-2005, 11:45 PM   #3
lowpro2k3
Member
 
Registered: Oct 2003
Location: Canada
Distribution: Slackware
Posts: 340

Rep: Reputation: 30
Re: increase code speed

Quote:
Originally posted by lmvent
Any hints for me??
First figure out the algorithm, on paper, then it will be trivial to implement in code
 
Old 10-21-2005, 08:37 AM   #4
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Do i need nested for loops??
 
Old 10-21-2005, 09:42 AM   #5
misterscorp
LQ Newbie
 
Registered: Oct 2005
Posts: 7

Rep: Reputation: 0
i think a pseudocode will go like this..

#define N 20 /* Use small number for testing*/
main() {
int arrIntegers[N]; /* array of Integers*/
for(i=0;i<n;i++)
initialize arrIntegers[i];
for(i=2;i<n;i++)
mark the multiples of i;
/* this marking can be done with
one 'for' and one 'if' stmt */
for(i=2;i<n;i++)
print the unmarked entries of it;
}
try to implement this ....
 
Old 10-21-2005, 10:37 AM   #6
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
sorry I forgot to mention I can't use arrays. I am in a first year class and we haven't gotten there yet.
 
Old 10-21-2005, 12:11 PM   #7
NineBreaker104
Newbie
 
Registered: Oct 2005
Posts: 1

Rep: Reputation: 0
Re: increase code speed

Quote:
Originally posted by lmvent
Code:
    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 << " ";
                nPrimes = nPrimes + 1;
            }
    }
The key part is this section of the code. What you are essentially doing is checking to see if i is divisible by j, where j are numbers between 2 and the value of i. The trick to this problem is that when you are trying to see if a number is prime, you don't have to check from 2 to the value of i. You can only have to check from 2 to the squartroot of i. Example:

i = 33. Your current code divides 33 with every value from 2 to 32. However, all you have to do is divide with every value from 2 to the squrtroot of 33 (it rounds down to 5). Why? Because we know that 33 is divisible by 3, which makes it a non-Prime value.

Bottom line, you don't have to check from 2 to the value of i to see if a number is prime or not. So, instead, find the squareroot of i, and check from to 2 that new value.

I hope I didn't explain it too confusingly.
 
Old 10-21-2005, 03:12 PM   #8
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
wow that definitely helps a lot! Thanks! If I need more help after I work on it, I'll be back
 
Old 10-25-2005, 10:50 PM   #9
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Code:
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    vector<int>primes;
    for (int i = 2; i <= maxN; i = i + 1)
    {   primes.push_back(i);
        for (int j = 2; j < i && j <= n; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    for (int i = 0; i < primes.size(); i = i + 1)
    {   cout << primes[i] << " ";
    }
    cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n"; 
    return 0;
}
This is my code now and runs about 1000 times faster than my professor's, but to get full credit it has to be more than 5000 times faster. He said to get it that fast the algorithm has to be redesigned and vectors need to be used in a clever way. Any hints now??
 
Old 10-26-2005, 04:10 AM   #10
enemorales
Member
 
Registered: Jul 2004
Location: Santiago, Chile
Distribution: Ubuntu
Posts: 410

Rep: Reputation: 30
We are now supposed to do your homework, so I'll only give you a hint: save the numbers you already now that are primes and use them!
 
Old 10-26-2005, 05:37 AM   #11
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,287

Rep: Reputation: 173Reputation: 173
remember you only need to check odd numbers.
 
Old 10-26-2005, 08:19 AM   #12
Orkie
Member
 
Registered: Mar 2005
Distribution: Breezy Badger
Posts: 248

Rep: Reputation: 30
2 is a prime number.
 
Old 10-26-2005, 08:23 AM   #13
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,287

Rep: Reputation: 173Reputation: 173
hmm, do you think maybe there are any more?
 
Old 10-26-2005, 10:27 AM   #14
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Code:
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    vector<int>primes;
    for(int i = 2; i <= n ; i = i + 1)
    {   primes.push_back(i);
        for(int j = 2; j <= (int)sqrt(static_cast<float>(n)) && j < i; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    int m = primes.size() - 1;
    for(int i = n + 1; i <= maxN; i = i + 1)
    {   primes.push_back(i);
        for(int j = 0; j <= m; j = j + 1)
        {   if(i%primes[j] == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    //for(int j = 0; j < primes.size(); j = j + 1)
    //{   cout << primes[j] << " ";
    //}
    cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n";
    return 0;
}
Okay, this is what I have now. It is a little bit faster, but not quite fast enough. He said the algorithm needs to be redesigned, but I can't think of another way to check if a number is prime. Any hints on that??
 
Old 10-26-2005, 12:12 PM   #15
jtshaw
Senior Member
 
Registered: Nov 2000
Location: Seattle, WA USA
Distribution: Ubuntu @ Home, RHEL @ Work
Posts: 3,892
Blog Entries: 1

Rep: Reputation: 66
I can think of two things right away.. first off, your outer loop should probably increment by 2 instead of 1 (should make it take half the time... because you know 2 is the only even prime). Second thing... if your afraid the vector operation is costly.. Check to see if the number is prime before you push it on the vector. This will save you many vector operations if maxN is a large number.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to increase speed of firefox!!!!!!! Lier Linux - Software 3 08-16-2005 05:00 PM
how to increase booting speed linuxaddict Linux - General 4 11-17-2003 12:17 PM
SPEED : How to increase? isone Linux - Newbie 1 10-29-2003 04:29 AM
increase hd speed saavik Linux - Hardware 3 07-23-2003 10:54 AM
Comcast speed increase tarballedtux Linux - Networking 0 03-01-2002 11:45 AM


All times are GMT -5. The time now is 03:48 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration