Printing prime numbers from 1 through 100

by

Three ways:

1.

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

2.

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

3.

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

Edit: In the third example, we keep track of all of our previously calculated primes. If a number is divisible by a non-prime number, there is also some prime <= that divisor which it is also divisble by. This reduces computation by a factor of primes_in_range/total_range.

More Related Contents:

  1. Which is the fastest algorithm to find prime numbers?
  2. Determining if a number is prime
  3. Fastest algorithm for primality test [closed]
  4. C++ – Printing prime numbers till N [closed]
  5. Algorithm (especially for c++) to show Every Permutation
  6. Random generation of numbers? [closed]
  7. What is the fastest way to transpose a matrix in C++?
  8. Rounding up to the nearest multiple of a number
  9. Why will std::sort crash if the comparison function is not as operator
  10. Magic number in boost::hash_combine
  11. Creating all possible k combinations of n items in C++
  12. Finding all the subsets of a set
  13. How do I calculate the week number given a date?
  14. Where can I get a “useful” C++ binary search algorithm?
  15. Enumerate factors of a number directly in ascending order without sorting?
  16. C++: Converting Hexadecimal to Decimal
  17. Circular lock-free buffer
  18. Generating m distinct random numbers in the range [0..n-1]
  19. Special simple random number generator
  20. Efficiently getting all divisors of a given number
  21. How can std::make_heap be implemented while making at most 3N comparisons?
  22. Writing a simple equation parser
  23. What is the right approach when using STL container for median calculation?
  24. Howto create combinations of several vectors without hardcoding loops in C++?
  25. Ways to do modulo multiplication with primitive types
  26. Removing ‘#include ‘ doesn’t break the code
  27. What’s time complexity of this algorithm for finding all combinations?
  28. How to find and replace all occurrences of a substring in a string?
  29. Finding square root without using sqrt function?
  30. Order Statistic Tree in C++

Leave a Comment