Escriba un programa para imprimir todos los números de Sophie Germain por menos de n. Un número primo p se llama número primo de Sophie si 2p+1 también es un número primo. El número 2p+1 se llama primo seguro . Por ejemplo, 11 es un número primo y 11*2 + 1 = 23 también es un número primo, entonces 11 es el número primo de Sophie Germain. Los primeros números primos de Sophie Germain son 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179…
Ejemplos:
Input : 25 Output : 2 3 5 11 23
Aquí está el programa para imprimir el número de Sophie Germain debajo de n.
La solución a esto es simple. Para obtener todos los números de Sophie debajo de n, haremos un ciclo hasta n y para cada número en el ciclo podemos verificar si ese número y (2*número + 1) son primos o no, y para verificar esto tenemos utilizó el método de la criba de Eratóstenes .
A continuación se muestra la implementación de este enfoque.
C++
// CPP program to print all sophie germain
// prime number till n.
#include <bits/stdc++.h>
using namespace std;
// function to detect prime number
// here we have used sieve method
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// to detect prime number
bool sieve(int n, bool prime[])
{
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
}
void printSophieGermainNumber(int n)
{
// We have made array till 2*n +1
// so that we can check prime number
// till that and conclude about sophie
// germain prime .
bool prime[2 * n + 1];
memset(prime, true, sizeof(prime));
sieve(2 * n + 1, prime);
for (int i = 2; i <= n; ++i) {
// checking every i whether it is
// sophie germain prime or not.
if (prime[i] && prime[2 * i + 1])
cout << i << " ";
}
}
int main()
{
int n = 25;
printSophieGermainNumber(n);
return 0;
}
Java
// Java program to print all
// sophie germain prime number till n.
import java.io.*;
import java.util.*;
class GFG {
// function to detect prime number
// here we have used sieve method
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// to detect prime number
static void sieve(int n, boolean prime[])
{
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i < n; i += p)
prime[i] = false;
}
}
}
static void printSophieGermainNumber(int n)
{
// We have made array till 2*n +1
// so that we can check prime number
// till that and conclude about sophie
// germain prime .
boolean prime[]=new boolean[2 * n + 1];
Arrays.fill(prime,true);
sieve(2 * n + 1, prime);
for (int i = 2; i < n; ++i) {
// checking every i whether it is
// sophie germain prime or not.
if (prime[i] && prime[2 * i + 1])
System.out.print( i + " ");
}
}
public static void main(String args[])
{
int n = 25;
printSophieGermainNumber(n);
}
}
// This code is contributed
// by Nikita Tiwari.
Python3
# Python 3 program to print all sophie # germain prime number till n. # Function to detect prime number # here we have used sieve method # https://www.geeksforgeeks.org/sieve-of-eratosthenes/ # to detect prime number def sieve(n, prime) : p = 2 while( p * p <= n ): # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Update all multiples of p for i in range(p * 2, n, p) : prime[i] = False p += 1 def printSophieGermainNumber(n) : # We have made array till 2*n +1 # so that we can check prime number # till that and conclude about sophie # germain prime . prime = [True]*(2 * n + 1) sieve(2 * n + 1, prime) for i in range(2, n + 1) : # checking every i whether it is # sophie germain prime or not. if (prime[i] and prime[2 * i + 1]) : print( i , end = " ") # Driver Code n = 25 printSophieGermainNumber(n) # This code is contributed by Nikita Tiwari.
C#
// C# program to print
// all sophie germain
// prime number till n.
using System;
class GFG
{
// function to detect prime
// number here we have used
// sieve method
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// to detect prime number
static void sieve(int n,
bool []prime)
{
for (int p = 2;
p * p <= n; p++)
{
// If prime[p] is
// not changed, then
// it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i = p * 2;
i < n; i += p)
prime[i] = false;
}
}
}
static void printSophieGermainNumber(int n)
{
// We have made array till
// 2*n +1 so that we can
// check prime number till
// that and conclude about
// sophie germain prime .
bool []prime = new bool[2 * n + 1];
for (int i = 0;
i < prime.Length; i++)
{
prime[i] = true;
}
sieve(2 * n + 1, prime);
for (int i = 2; i < n; ++i)
{
// checking every i whether
// it is sophie germain prime
// or not.
if (prime[i] && prime[2 * i + 1])
Console.Write( i + " ");
}
}
// Driver code
static void Main()
{
int n = 25;
printSophieGermainNumber(n);
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to print
// all sophie germain
// prime number till n.
// function to detect prime
// number here we have used
// sieve method
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// to detect prime number
function sieve($n, &$prime)
{
for ($p = 2;
$p * $p <= $n; $p++)
{
// If prime[p] is
// not changed, then
// it is a prime
if ($prime[$p] == true)
{
// Update all
// multiples of p
for ($i = $p * 2;
$i <= $n; $i += $p)
$prime[$i] = false;
}
}
}
function printSophieGermainNumber($n)
{
// We have made array till
// 2*n +1 so that we can
// check prime number till
// that and conclude about
// sophie germain prime .
$prime = array();
for($i = 0;
$i < (2 * $n + 1); $i++)
$prime[$i] = true;
sieve(2 * $n + 1, $prime);
for ($i = 2; $i <= $n; ++$i)
{
// checking every i
// whether it is sophie
// germain prime or not.
if ($prime[$i] &&
$prime[2 * $i + 1])
echo ($i . " ");
}
}
// Driver code
$n = 25;
printSophieGermainNumber($n);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript program to print
// all sophie germain
// prime number till n.
// function to detect prime
// number here we have used
// sieve method
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// to detect prime number
function sieve(n, prime)
{
for (let p = 2; p * p <= n; p++)
{
// If prime[p] is
// not changed, then
// it is a prime
if (prime[p] == true)
{
// Update all
// multiples of p
for (let i = p * 2;
i <= n; i += p)
prime[i] = false;
}
}
}
function printSophieGermainNumber(n)
{
// We have made array till
// 2*n +1 so that we can
// check prime number till
// that and conclude about
// sophie germain prime .
let prime = new Array();
for(let i = 0; i < (2 * n + 1); i++)
prime[i] = true;
sieve(2 * n + 1, prime);
for (let i = 2; i <= n; ++i)
{
// checking every i
// whether it is sophie
// germain prime or not.
if (prime[i] &&
prime[2 * i + 1])
document.write(i + " ");
}
}
// Driver code
let n = 25;
printSophieGermainNumber(n);
// This code is contributed by
// gfgking
</script>
Producción :
2 3 5 11 23
Aplicación de los números primos de Sophie:
1. Se utiliza en criptografía como primos seguros que se convierten en factores de una clave secreta en el criptosistema RSA .
2. En la primera versión de AKS Primality Test, se usa para reducir la complejidad del peor de los casos.
3. Se utiliza en la generación de Pseudo Random Number .
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA