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