Click here to Skip to main content
15,891,880 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
I wrote this code to show the primes between 1 and 100. The only condition is to do not use functions, whole code should be inline. I would ask if I can improve (optimize) it much more?

C++
#include<iostream>

using namespace std;
int main() {
    int i=2,j=2;
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    while(i!=100) {
        for(int j=2;j<i;j++) {
            if(i%j==0)
            break;

            if(j==i-1)
            cout<<i<<"\t";
        }

        i++;
    }

    cout<<endl;
    system("pause");
    return 0;
}
Posted

Well...there is a very simple improvement you could make to halve the number of loops...

Think about it: how many Prime Numbers are Even?
So, why are you testing them all?
 
Share this answer
 
There are many algorithms that you can use to calculate primes. The question really is, what defines worthwhile optimisation? Are you trying to reduce the time taken to calculate the primes - which on only 100 values is going to be pretty darned fast using the implementation you have here. Are you looking for a more elegant solution? Really, the answer to your question depends entirely on what you are trying to achieve. For instance, if you used the Sieve of Erastothsenese, your code will look more complex but you will have implemented a solution that is capable of coping with larger primes more efficiently than this code.
 
Share this answer
 
You are checking every number from 2 to 100. But since 2 is the only even prime number, you can skip every even number after 2. This goes for both i and j. So start i and j at 3, and increment them by 2.

C++
#include<iostream>

using namespace std;

int main() {
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    for (int i=3; i<100;i+=2) {
        // This loop stops either when j*j>i or when i is divisible by j.
        // The first condition means prime, the second, not prime.
        int j=3;
        for(;j*j<=i && i%j!=0; j+=2); // No loop body

        if (j*j>i) cout << i << "\t";
    }
    cout<<endl;
    return 0;
}</iostream>


In addition to the trick mentioned above, I've added the condition j*j<=i which logically is the exact same as j<=sqrt(i). There's no need to compute the square root when you can do a simple multiplication.
 
Share this answer
 
Comments
h_t 6-Feb-14 11:21am    
thanks to all

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900