Posted on by Kalkicode
Code Mathematics

Print all sophie germain primes less than n

Sophie Germain primes are a special class of prime numbers that are closely related to safe primes. A Sophie Germain prime is a prime number p such that 2p + 1 is also prime. These primes have interesting properties and applications in number theory and cryptography.

Problem Statement

The problem is to find and print all Sophie Germain primes that are less than a given positive integer n.

Idea to Solve the Problem

To solve this problem, we can use the Sieve of Eratosthenes algorithm to generate a list of prime numbers up to 2n. Then, for each prime number p in the list, we check whether 2p + 1 is also prime. If both p and 2p + 1 are prime, then p is a Sophie Germain prime, and we print it.

Pseudocode

``````
method eratosthenesSieve(prime, n)
for i from 0 to n
prime[i] = true
prime[0] = false
prime[1] = false
for i from 2 to n
if prime[i] is true
for j from i * i to n step i
prime[j] = false

method sophieGermainPrime(n)
if n < 1
return

print "Given n:", n
k = n + n
prime = new boolean[k + 1]
eratosthenesSieve(prime, k)
p = 0
for i from 2 to n
if prime[i] is true
p = (i * 2) + 1
if p <= k and prime[p] is not false
print i
``````

Algorithm Explanation

1. The `eratosthenesSieve` method implements the Sieve of Eratosthenes algorithm to find all prime numbers up to `n`. It marks non-prime numbers as `false` in the `prime` array.

2. The `sophieGermainPrime` method takes a positive integer `n` as input.

3. If `n` is less than 1, the method returns immediately to handle invalid inputs.

4. Initialize an array `prime` of booleans, where `prime[i]` is `true` if `i` is prime.

5. Call the `eratosthenesSieve` method to generate the prime numbers up to `2n`.

6. Loop through the prime numbers less than or equal to `n`. For each prime `i`, calculate `2i + 1` and check if it's prime as well.

7. If both `i` and `2i + 1` are prime, print `i`.

Code Solution

``````import java.util.ArrayList;
// Java program for
// Print all sophie germain primes less than n
{
public void eratosthenesSieve(boolean[] prime, int n)
{
// Set all element as prime
for (int i = 0; i <= n; ++i)
{
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
public void sophieGermainPrime(int n)
{
if (n < 1)
{
return;
}
System.out.println("\n  Given n : " + n);
int k = n + n;
boolean[] prime = new boolean[k + 1];
eratosthenesSieve(prime, k);
int p = 0;
// Display sophie germain prime (2..n)
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
p = (i * 2) + 1;
if (p <= k && prime[p] != false)
{
System.out.print("  " + i);
}
}
}
}
public static void main(String[] args)
{
// Test
}
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Print all sophie germain primes less than n
{
public: void eratosthenesSieve(bool prime[], int n)
{
// Set all element as prime
for (int i = 0; i <= n; ++i)
{
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
for (int j = i *i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
void sophieGermainPrime(int n)
{
if (n < 1)
{
return;
}
cout << "\n  Given n : " << n << endl;
int k = n + n;
bool prime[k + 1];
this->eratosthenesSieve(prime, k);
int p = 0;
// Display sophie germain prime (2..n)
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
p = (i *2) + 1;
if (p <= k && prime[p] != false)
{
cout << "  " << i;
}
}
}
}
};
int main()
{
// Test
return 0;
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````// Include namespace system
using System;
// Csharp program for
// Print all sophie germain primes less than n
{
public void eratosthenesSieve(Boolean[] prime, int n)
{
// Set all element as prime
for (int i = 0; i <= n; ++i)
{
prime[i] = true;
}
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
public void sophieGermainPrime(int n)
{
if (n < 1)
{
return;
}
Console.WriteLine("\n  Given n : " + n);
int k = n + n;
Boolean[] prime = new Boolean[k + 1];
this.eratosthenesSieve(prime, k);
int p = 0;
// Display sophie germain prime (2..n)
for (int i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
p = (i * 2) + 1;
if (p <= k && prime[p] != false)
{
Console.Write("  " + i);
}
}
}
}
public static void Main(String[] args)
{
// Test
}
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````package main
import "fmt"
// Go program for
// Print all sophie germain primes less than n

func eratosthenesSieve(prime[] bool, n int) {
// Set all element as prime
for i := 0 ; i <= n ; i++ {
prime[i] = true
}
prime[0] = false
prime[1] = false
for i := 2 ; i <= n ; i++ {
if prime[i] == true {
for j := i * i ; j <= n ; j += i {
prime[j] = false
}
}
}
}
func sophieGermainPrime(n int) {
if n < 1 {
return
}
fmt.Println("\n  Given n : ", n)
var k int = n + n
var prime = make([] bool, k + 1)
eratosthenesSieve(prime, k)
var p int = 0
// Display sophie germain prime (2..n)
for i := 2 ; i <= n ; i++ {
if prime[i] == true {
p = (i * 2) + 1
if p <= k && prime[p] != false {
fmt.Print("  ", i)
}
}
}
}
func main() {

// Test
sophieGermainPrime(100)
sophieGermainPrime(300)
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````<?php
// Php program for
// Print all sophie germain primes less than n
{
public	function eratosthenesSieve(&\$prime, \$n)
{
// Set all element as prime
\$prime[0] = false;
\$prime[1] = false;
for (\$i = 2; \$i <= \$n; ++\$i)
{
if (\$prime[\$i] == true)
{
for (\$j = \$i * \$i; \$j <= \$n; \$j += \$i)
{
\$prime[\$j] = false;
}
}
}
}
public	function sophieGermainPrime(\$n)
{
if (\$n < 1)
{
return;
}
echo("\n  Given n : ".\$n.
"\n");
\$k = \$n + \$n;
// Set all element as prime
\$prime = array_fill(0, \$k + 1, true);
\$this->eratosthenesSieve(\$prime, \$k);
\$p = 0;
// Display sophie germain prime (2..n)
for (\$i = 2; \$i <= \$n; ++\$i)
{
if (\$prime[\$i] == true)
{
\$p = (\$i * 2) + 1;
if (\$p <= \$k && \$prime[\$p] != false)
{
echo("  ".\$i);
}
}
}
}
}

function main()
{
// Test
}
main();``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````// Node JS program for
// Print all sophie germain primes less than n
{
eratosthenesSieve(prime, n)
{
// Set all element as prime
prime[0] = false;
prime[1] = false;
for (var i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
for (var j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
sophieGermainPrime(n)
{
if (n < 1)
{
return;
}
console.log("\n  Given n : " + n);
var k = n + n;
// Set all element as prime
var prime = Array(k + 1).fill(true);
this.eratosthenesSieve(prime, k);
var p = 0;
// Display sophie germain prime (2..n)
for (var i = 2; i <= n; ++i)
{
if (prime[i] == true)
{
p = (i * 2) + 1;
if (p <= k && prime[p] != false)
{
process.stdout.write("  " + i);
}
}
}
}
}

function main()
{
// Test
}
main();``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````#  Python 3 program for
#  Print all sophie germain primes less than n
def eratosthenesSieve(self, prime, n) :
#  Set all element as prime
prime[0] = False
prime[1] = False
i = 2
while (i <= n) :
if (prime[i] == True) :
j = i * i
while (j <= n) :
prime[j] = False
j += i

i += 1

def sophieGermainPrime(self, n) :
if (n < 1) :
return

print("\n  Given n : ", n)
k = n + n
#  Set all element as prime
prime = [True] * (k + 1)
self.eratosthenesSieve(prime, k)
p = 0
i = 2
#  Display sophie germain prime (2..n)
while (i <= n) :
if (prime[i] == True) :
p = (i * 2) + 1
if (p <= k and prime[p] != False) :
print("  ", i, end = "")

i += 1

def main() :
#  Test

if __name__ == "__main__": main()``````

Output

``````  Given n :  100
2   3   5   11   23   29   41   53   83   89
Given n :  300
2   3   5   11   23   29   41   53   83   89   113   131   173   179   191   233   239   251   281   293``````
``````#  Ruby program for
#  Print all sophie germain primes less than n
def eratosthenesSieve(prime, n)
#  Set all element as prime
prime[0] = false
prime[1] = false
i = 2
while (i <= n)
if (prime[i] == true)
j = i * i
while (j <= n)
prime[j] = false
j += i
end

end

i += 1
end

end

def sophieGermainPrime(n)
if (n < 1)
return
end

print("\n  Given n : ", n, "\n")
k = n + n
#  Set all element as prime
prime = Array.new(k + 1) {true}
self.eratosthenesSieve(prime, k)
p = 0
i = 2
#  Display sophie germain prime (2..n)
while (i <= n)
if (prime[i] == true)
p = (i * 2) + 1
if (p <= k && prime[p] != false)
print("  ", i)
end

end

i += 1
end

end

end

def main()
#  Test
end

main()``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````// Scala program for
// Print all sophie germain primes less than n
{
def eratosthenesSieve(prime: Array[Boolean], n: Int): Unit = {
// Set all element as prime
prime(0) = false;
prime(1) = false;
var i: Int = 2;
while (i <= n)
{
if (prime(i) == true)
{
var j: Int = i * i;
while (j <= n)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
}
def sophieGermainPrime(n: Int): Unit = {
if (n < 1)
{
return;
}
println("\n  Given n : " + n);
var k: Int = n + n;
// Set all element as prime
var prime: Array[Boolean] = Array.fill[Boolean](k + 1)(true);
eratosthenesSieve(prime, k);
var p: Int = 0;
var i: Int = 2;
// Display sophie germain prime (2..n)
while (i <= n)
{
if (prime(i) == true)
{
p = (i * 2) + 1;
if (p <= k && prime(p) != false)
{
print("  " + i);
}
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Test
}
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````
``````// Swift 4 program for
// Print all sophie germain primes less than n
{
func eratosthenesSieve(_ prime: inout[Bool], _ n: Int)
{
// Set all element as prime
prime[0] = false;
prime[1] = false;
var i: Int = 2;
while (i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
func sophieGermainPrime(_ n: Int)
{
if (n < 1)
{
return;
}
print("\n  Given n : ", n);
let k: Int = n + n;
// Set all element as prime
var prime: [Bool] = Array(repeating: true, count: k + 1);
self.eratosthenesSieve(&prime, k);
var p: Int = 0;
var i: Int = 2;
// Display sophie germain prime (2..n)
while (i <= n)
{
if (prime[i] == true)
{
p = (i * 2) + 1;
if (p <= k && prime[p]  != false)
{
print("  ", i, terminator: "");
}
}
i += 1;
}
}
}
func main()
{
// Test
}
main();``````

Output

``````  Given n :  100
2   3   5   11   23   29   41   53   83   89
Given n :  300
2   3   5   11   23   29   41   53   83   89   113   131   173   179   191   233   239   251   281   293``````
``````// Kotlin program for
// Print all sophie germain primes less than n
{
fun eratosthenesSieve(prime: Array < Boolean > , n: Int): Unit
{
// Set all element as prime
prime[0] = false;
prime[1] = false;
var i: Int = 2;
while (i <= n)
{
if (prime[i] == true)
{
var j: Int = i * i;
while (j <= n)
{
prime[j] = false;
j += i;
}
}
i += 1;
}
}
fun sophieGermainPrime(n: Int): Unit
{
if (n < 1)
{
return;
}
println("\n  Given n : " + n);
val k: Int = n + n;
// Set all element as prime
var prime: Array < Boolean > = Array(k + 1)
{
true
};
this.eratosthenesSieve(prime, k);
var p: Int ;
var i: Int = 2;
// Display sophie germain prime (2..n)
while (i <= n)
{
if (prime[i] == true)
{
p = (i * 2) + 1;
if (p <= k && prime[p] != false)
{
print("  " + i);
}
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

Output

``````  Given n : 100
2  3  5  11  23  29  41  53  83  89
Given n : 300
2  3  5  11  23  29  41  53  83  89  113  131  173  179  191  233  239  251  281  293``````

Time Complexity

The time complexity of this algorithm is primarily determined by the Sieve of Eratosthenes. Generating prime numbers using the sieve has a time complexity of O(n log log n), and checking the primality of each `2i + 1` has a time complexity of O(log log n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post