Question

Define in Scheme an infinite stream consisting of twin prime numbers. All primes ? with the property that ? + 2 or ? − 2 are also prime should be included, each one only once. Hint: Apply the Sieve of Eratosthenes.

Answer 1

ANSWER:

Prime Number : Number that is divisible by only itself and 1 is called prime number.

Twin Prime : Pair of prime numbers having difference of 2.
let's say p1 and p2 are two prime numbers with p2 > p1
the they are said to be twin prime if p2 - p1 = 2.
example : p1 = 3, p2 = 5
p1 = 11 p2 = 13

Algorithm Design : We use Sieve of Eratosthenes to generate the infinite stream of twin primes.
1) we will find all prime numbers.
2) we will iterate through the list to check for twin primes.
3) condition for twin primes :
p1, p2 are prime and p2 - p1 = 2

c++ implementation :

#include <bits/stdc++.h>
using namespace std;

/ define infinte a number for the program as /
// we can not can not run the program for infinity
#define infinte 100000

// map to store the twin prime numbers
map <int, int> twinPrime;
map <int, int> :: iterator it;

// Sieve of eratosthenes to calculate the twin prime numbers
// and store them into map
void TwinPrime() {
/ Create a boolean array isprime[] /
/ and initialize all entries till infinite it as true. /
/ isprime[p] will be false if p is not prime /
/ isprime[p] will be true if p is prime /
bool isprime[infinte];

for(int i = 1;i <= infinte;i++) {
isprime[i] = true;
}

for(int i = 2;i*i <= infinte;i++) {

// for every number i which is factor of it's
// multiples, mark it's multiple as false
// as they can be factorized into i
// so they are not prime

if(isprime[i] == true) {
// multiples of i
for(int j = i * 2;j <= infinte;j += i) {
// mark the multipels as false
isprime[j] = false;
}
}

}
int j = 0;

// check for the twin primes
// if i and i+2 are primes then
// they will be twin primes
// as i+2 - i = 2

for(int i = 2;i <= infinte - 2;i++) {
if(isprime[i] && isprime[i+2]) {
// store into map
twinPrime[i]++;
twinPrime[i+2]++;
}
}
// print the twin primes.
cout << "Twin Prime Numbers are : ";
for(it = twinPrime.begin();it != twinPrime.end();it++) {
cout << it->first << " ";
}
}

// driver main function
int main()
{
// call the TwinPrime fucntion to find
// all the twin prime numbers
TwinPrime();

return 0;
}

images :

Output Screenshot :