Sexy Primzahl
In der Mathematik sind Sexy Primes Primzahlen, die sich um sechs voneinander unterscheiden. Zum Beispiel sind die Zahlen 5 und 11 beide sexy Primzahlen, weil sie sich um 6 unterscheiden. Wenn p + 2 oder p + 4 (wobei p die untere Primzahl ist) ebenfalls eine Primzahl ist.
Sie können wie folgt gruppiert werden:
- Sexy Primzahlenpaare: Es hat die Form (p, p + 6), wobei p und p + 6 Primzahlen sind.
Z.B. (11, 17) ist ein sexy Primzahlpaar.
- Sexy Primzahl-Tripletts: Primzahl-Tripletts (p, p + 6, p + 12), bei denen p + 18 zusammengesetzt ist, werden als sexy Primzahl-Tripletts bezeichnet.
Z.B. (7, 13, 19) ist ein sexy Prime Drilling.
- Sexy Primzahlvierlinge: Sexy Primzahlvierlinge (p, p + 6, p + 12, p + 18) können nur mit Primzahlen beginnen, die in ihrer dezimalen Darstellung auf eine 1 enden (außer dem Vierling mit p = 5).
Z.B. (41, 47, 53, 59) ist ein sexy Prime-Vierer.
- Sexy Primzahl-Fünflinge: Bei einer arithmetischen Folge von fünf Gliedern mit gemeinsamer Differenz 6 muss eines der Glieder durch 5 teilbar sein, da die beiden Zahlen teilerfremd sind. Somit ist das einzige reizvolle Primzahlquintolle (5, 11, 17, 23, 29); keine Folge von sexy Primzahlen mehr möglich.
Gegeben sei ein Bereich der Form [L, R] . Die Aufgabe besteht darin, alle sexy Prime-Paare im Sortiment zu drucken.
Beispiele:
Input : L = 6, R = 59 Output : (7, 13) (11, 17) (13, 19) (17, 23) (23, 29) (31, 37) (37, 43) (41, 47) (47, 53) (53, 59) Input : L = 1, R = 19 Output : (5, 11) (7, 13) (11, 17) (13, 19)
Sexy Prime innerhalb einer Reichweite [L, R] kann mit Sieve Of Eratosthenes generiert werden . Die Idee ist, ein boolsches Array von Sieve zu generieren und eine i-Schleife von L bis R – 6 (einschließlich) auszuführen und zu prüfen, ob i und i + 6 Primzahlen sind oder nicht. Wenn beide Primzahlen sind, geben Sie beide Zahlen aus.
Unten ist die Implementierung dieses Ansatzes:
C++
// CPP Program to print sexy prime in a range.
#include <bits/stdc++.h>
using namespace std;
// Print the sexy prime in a range
void sexyprime(int l, int r)
{
// Sieve Of Eratosthenes for generating
// prime number.
bool prime[r + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= r; 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 <= r; i += p)
prime[i] = false;
}
}
// From L to R - 6, checking if i,
// i + 6 are prime or not.
for (int i = l; i <= r - 6; i++)
if (prime[i] && prime[i + 6])
cout << "(" << i << ", "
<< i + 6 << ") ";
}
// Driven Program
int main()
{
int L = 6, R = 59;
sexyprime(L, R);
return 0;
}
Java
// Java code to print sexy prime in a range.
import java.util.Arrays;
import java.util.Collections;
class GFG
{
// Print the sexy prime in a range
public static void sexyprime(int l, int r)
{
// Sieve Of Eratosthenes for generating
// prime number.
boolean [] prime= new boolean[r + 1];
// memset(prime, true, sizeof(prime));
Arrays.fill(prime, true);
for (int p = 2; p * p <= r; 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 <= r; i += p)
prime[i] = false;
}
}
// From L to R - 6, checking if i,
// i + 6 are prime or not.
for (int i = l; i <= r - 6; i++)
if (prime[i] && prime[i + 6])
System.out.print( "(" + i + ", "
+ (i + 6) + ") ");
}
// Driver program to test above methods
public static void main(String[] args)
{
int L = 6, R = 59;
sexyprime(L, R);
}
}
// This code is contributed by Chhavi
Python 3
# Python 3 Program to print
# sexy prime in a range.
# Print the sexy prime in a range
def sexyprime(l, r) :
# Sieve Of Eratosthenes
# for generating
# prime number.
prime=[True] * (r + 1)
p = 2
while(p * p <= r) :
# 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, r+1 ,p) :
prime[i] = False
p = p + 1
# From L to R - 6, checking if i,
# i + 6 are prime or not.
for i in range( l,r - 6 + 1) :
if (prime[i] and prime[i + 6]) :
print("(", i , ",", i + 6,")", end="")
# Driven Program
L = 6
R = 59
sexyprime(L, R)
# This code is contributed by Nikita Tiwari.
C#
// C# code to print sexy
// prime in a range.
using System;
class GFG
{
// Print the sexy
// prime in a range
public static void sexyprime(int l,
int r)
{
// Sieve Of Eratosthenes
// for generating prime number.
int[] prime = new int[r + 1];
// memset(prime, true,
// sizeof(prime));
for (int i = 0; i < r + 1; i++)
prime[i] = 1;
for (int p = 2; p * p <= r; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == 1)
{
// Update all multiples of p
for (int i = p * 2;
i <= r; i += p)
prime[i] = 0;
}
}
// From L to R - 6, checking
// if i, i + 6 are prime or not.
for (int i = l; i <= r - 6; i++)
if (prime[i] == 1 && prime[i + 6] == 1)
Console.Write("(" + i + ", " +
(i + 6) + ") ");
}
// Driver Code
public static void Main()
{
int L = 6, R = 59;
sexyprime(L, R);
}
}
// This code is contributed by mits
PHP
<?php
// PHP Program to print
// sexy prime in a range.
// Print the sexy
// prime in a range
function sexyprime($l, $r)
{
// Sieve Of Eratosthenes for
// generating prime number.
$prime = array_fill(0, $r + 1,
true);
for ($p = 2;
$p * $p <= $r; $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 <= $r; $i += $p)
$prime[$i] = false;
}
}
// From L to R - 6,
// checking if i,
// i + 6 are prime or not.
for ($i = $l; $i <= $r - 6; $i++)
if ($prime[$i] &&
$prime[$i + 6])
echo "(" , $i , ", ",
$i + 6 , ") ";
}
// Driver Code
$L = 6;
$R = 59;
sexyprime($L, $R);
// This code is contributed
// by ajit.
?>
Javascript
<script>
// Javascript Program to print sexy prime in a range.
// Print the sexy prime in a range
function sexyprime(l, r)
{
// Sieve Of Eratosthenes for generating
// prime number.
var prime = Array(r+1).fill(true);
for (var p = 2; p * p <= r; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (var i = p * 2; i <= r; i += p)
prime[i] = false;
}
}
// From L to R - 6, checking if i,
// i + 6 are prime or not.
for (var i = l; i <= r - 6; i++)
if (prime[i] && prime[i + 6])
document.write( "(" + i + ", "
+ (i + 6) + ") ");
}
// Driven Program
var L = 6, R = 59;
sexyprime(L, R);
</script>
Ausgabe:
(7, 13) (11, 17) (13, 19) (17, 23) (23, 29) (31, 37) (37, 43) (41, 47) (47, 53) (53, 59)