Algorithms · C++

Sieve of Eratosthenes Algorithm

if we want to find prime numbers up to some predefined integer n, there are some steps to find the prime numbers. (trial division)

find primes (int arr[])

  1.  define empty list
  2. for from i = 2 to i = n
  3. if isPrime (i)
  4. if true (add i to list)

Implementation (Trial division) in c++ 

#include <iostream>
#include <vector>
using namespace std;

void find (int arr[], int length);
bool isPrime(int num);
int main() {
  int arr[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
  int length = sizeof (arr) / sizeof (arr[0]);
  find(arr, length);
 return 0;
}
void find(int arr[], int length) {
  vector <int> list;
  for (int i = 0; i < length; i++)
  {
     if ( isPrime(arr[i]) )
         list.push_back(arr[i]);
  }
  for (int i = 0; i < list.size()-1; i++)
         cout << list[i] << endl;
}
bool isPrime(int num)
{
  bool flag = true;
  if (num <= 2)
      flag = false;
  if (num % 2 == 0)
      flag = false;
  else 
  {
   for (int i = 2; i < num; i++)
   {
     if (num % i == 0)
        flag = false;
   }
  }
 return flag;
}

Complexity  

the time complexity of finding a list of primes with trial division is o(n √n)


Using Sieve of Eratosthenes algorithm

Sieve of Eratosthenes is a simple algorithm to find prime numbers.

Algorithm consists of two nested loops:

  1. outer: seeking for unmarked numbers (primes).
  2. inner: marking primes’ multiples as composites.
  • For all numbers m: 2 .. n, if m is unmarked:
    • add m to primes list;
    • mark all it’s multiples, lesser or equal, than n (k * m ≤ n, k ≥ 2);
  • otherwise, if m is marked, then it is a composite number.

 

Capture

Capture.PNG

Capture

Capture.PNG

Capture.PNG

Capture

Capture

Complexity 

computational complexity of the algorithm is O(nlog(log(n)))

Implementation in c++

 

#include <iostream>
using namespace std;
const int n = 100;

void SieveOfEratosthenes()
{
   bool prime[n+1];
   memset(prime, true, sizeof(prime));
   for (int p = 2; p*p <= n; p++)
   {
     if (prime[p] == true)
     {
       for (int i = p * 2; i <= n; i += p)
       prime[i] = false;
     }
   }
// Print all prime numbers
  for (int p = 2; p <= n; p++)
      if (prime[p])
  cout << p << " ";
}

int main()
{
  cout << "Following are the prime numbers smaller "
       << " than or equal to " << n << endl;
  SieveOfEratosthenes();
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s