Dado un número muy grande N (> 150), la tarea es comprobar si este número es primo, semiprimo o compuesto.
Ejemplo:
Entrada: N = 90000000
Salida: No primo
Explicación:
tenemos (N-1)%6 = 89999999%6 = 1 y
(N+1)%6 = 90000001%6 = 5
Dado que n-1 y n+1 no son divisible por 6
Por lo tanto, N = 90000000 no es primo
Entrada: N = 7894561
Salida: semiprimo
Explicación: aquí N = 7894561
= 71*111191
Dado que 71 y 111191 son primos, por lo tanto, 7894561 es semiprimo
Acercarse:
- Se puede observar que si n es un número primo entonces n+1 o n-1 será divisible por 6
- Si existe un número n tal que ni n+1 ni n-1 son divisibles por 6, entonces n no es un número primo
- Si existe un número n tal que n+1 o n-1 es divisible por 6, entonces n es un número primo o semiprimo
- Para diferenciar entre prima y semiprima, se utiliza el siguiente método:
- Si N es semiprimo entonces,
N = p*q ....................(1) where p & q are primes.
- Luego de la conjetura de Goldbach :
p + q must be even i.e, p + q = 2*n for any positive integer n
- Por lo tanto, resolver para p & q dará
p = n - sqrt(n2 - N) q = n + sqrt(n2 - N)
- Sea n 2 – N un cuadrado perfecto, entonces
n2 - N = m2, .................(2) for any positive integer m
- Resolviendo las ecuaciones (1) y (2) obtenemos
m = (q-p)/2 n = (p+q)/2
- Ahora, si la ecuación (1) y (2) se encuentran en algún punto, entonces existe un par (p, q) tal que el número N es semiprimo, de lo contrario, N es primo.
- La ecuación (2) forma triplete pitagórico
- La solución esperada varía en el gráfico.
Pseudocódigo:
- Ingrese un número N y si N – 1 y N + 1 no es divisible por 6, entonces el número N no es primo . de lo contrario es prima o semiprima
- Si n-1 o n+1 es divisible por 6, itere en el rango (raíz cuadrada (N) + 1, N) y encuentre un par (p, q) tal que p*q = N mediante la siguiente fórmula:
p = i - sqrt(i*i - N) q = n/p where i = index in range(sqrt(N) + 1, N)
- Si p*q = N entonces el número N es semiprimo, de lo contrario es primo
A continuación se muestra la implementación del enfoque anterior:
Java
import static java.lang.Math.sqrt;
public class Primmefunc {
public static void prime(long n)
{
int flag = 0;
// checking divisibility by 6
if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0) {
System.out.println("Not Prime");
}
else {
// breakout if number is perfect square
double s = sqrt(n);
if ((s * s) == n) {
System.out.println("Semi-Prime");
}
else {
long f = (long)s;
long l = (long)((f * f));
// Iterating over to get the
// closest average value
for (long i = f + 1; i < l; i++) {
// 1st Factor
long p = i - (long)(sqrt((i * i) - (n)));
// 2nd Factor
long q = n / p;
// To avoid Convergence
if (p < 2 || q < 2) {
break;
}
// checking semi-prime condition
if ((p * q) == n) {
flag = 1;
break;
}
// If convergence found
// then number is semi-prime
else {
// convergence not found
// then number is prime
flag = 2;
}
}
if (flag == 1) {
System.out.println("Semi-Prime");
}
else if (flag == 2) {
System.out.println("Prime");
}
}
}
}
public static void main(String[] args)
{
// Driver code
// Entered number should be greater
// than 300 to avoid Convergence of
// second factor to 1
prime(8179);
prime(7894561);
prime(90000000);
prime(841);
prime(22553);
prime(1187);
}
//written by Rushil Jhaveri
}
CPP
#include<bits/stdc++.h>
using namespace std ;
void prime(long n)
{
int flag = 0;
// checking divisibility by 6
if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0)
{
cout << ("Not Prime") << endl;
}
else
{
// breakout if number is perfect square
double s = sqrt(n);
if ((s * s) == n)
{
cout<<("Semi-Prime")<<endl;
}
else
{
long f = (long)s;
long l = (long)((f * f));
// Iterating over to get the
// closest average value
for (long i = f + 1; i < l; i++)
{
// 1st Factor
long p = i - (long)(sqrt((i * i) - (n)));
// 2nd Factor
long q = n / p;
// To avoid Convergence
if (p < 2 || q < 2)
{
break;
}
// checking semi-prime condition
if ((p * q) == n)
{
flag = 1;
break;
}
// If convergence found
// then number is semi-prime
else
{
// convergence not found
// then number is prime
flag = 2;
}
}
if (flag == 1)
{
cout<<("Semi-Prime")<<endl;
}
else if (flag == 2)
{
cout<<("Prime")<<endl;
}
}
}
}
// Driver code
int main()
{
// Entered number should be greater
// than 300 to avoid Convergence of
// second factor to 1
prime(8179);
prime(7894561);
prime(90000000);
prime(841);
prime(22553);
prime(1187);
}
// This code is contributed by Rajput-Ji
Python3
def prime(n):
flag = 0;
# checking divisibility by 6
if ((n + 1) % 6 != 0 and (n - 1) % 6 != 0):
print("Not Prime");
else:
# breakout if number is perfect square
s = pow(n, 1/2);
if ((s * s) == n):
print("Semi-Prime");
else:
f = int(s);
l = int(f * f);
# Iterating over to get the
# closest average value
for i in range(f + 1, l):
# 1st Factor
p = i - (pow(((i * i) - (n)), 1/2));
# 2nd Factor
q = n // p;
# To avoid Convergence
if (p < 2 or q < 2):
break;
# checking semi-prime condition
if ((p * q) == n):
flag = 1;
break;
# If convergence found
# then number is semi-prime
else:
# convergence not found
# then number is prime
flag = 2;
if (flag == 1):
print("Semi-Prime");
elif(flag == 2):
print("Prime");
# Driver code
if __name__ == '__main__':
# Entered number should be greater
# than 300 to avoid Convergence of
# second factor to 1
prime(8179);
prime(7894561);
prime(90000000);
prime(841);
prime(22553);
prime(1187);
# This code is contributed by 29AjayKumar
C#
using System;
public class Primmefunc
{
public static void prime(long n)
{
int flag = 0;
// checking divisibility by 6
if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0)
{
Console.WriteLine("Not Prime");
}
else
{
// breakout if number is perfect square
double s = Math.Sqrt(n);
if ((s * s) == n)
{
Console.WriteLine("Semi-Prime");
}
else
{
long f = (long)s;
long l = (long)((f * f));
// Iterating over to get the
// closest average value
for (long i = f + 1; i < l; i++)
{
// 1st Factor
long p = i - (long)(Math.Sqrt((i * i) - (n)));
// 2nd Factor
long q = n / p;
// To avoid Convergence
if (p < 2 || q < 2)
{
break;
}
// checking semi-prime condition
if ((p * q) == n)
{
flag = 1;
break;
}
// If convergence found
// then number is semi-prime
else
{
// convergence not found
// then number is prime
flag = 2;
}
}
if (flag == 1)
{
Console.WriteLine("Semi-Prime");
}
else if (flag == 2)
{
Console.WriteLine("Prime");
}
}
}
}
// Driver code
public static void Main(String[] args)
{
// Entered number should be greater
// than 300 to avoid Convergence of
// second factor to 1
prime(8179);
prime(7894561);
prime(90000000);
prime(841);
prime(22553);
prime(1187);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
function prime(n)
{
var flag = 0;
// checking divisibility by 6
if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0) {
document.write("Not Prime<br>");
}
else {
// breakout if number is perfect square
var s = parseInt(Math.sqrt(n));
if ((s * s) == n) {
document.write("Semi-Prime<br>");
}
else {
var f = s;
var l = ((f * f));
// Iterating over to get the
// closest average value
for (var i = f + 1; i < l; i++) {
// 1st Factor
var p = i - parseInt(Math.sqrt((i * i) - (n)));
// 2nd Factor
var q = parseInt(n / p);
// To avoid Convergence
if (p < 2 || q < 2) {
break;
}
// checking semi-prime condition
if ((p * q) == n) {
flag = 1;
break;
}
// If convergence found
// then number is semi-prime
else {
// convergence not found
// then number is prime
flag = 2;
}
}
if (flag == 1) {
document.write("Semi-Prime<br>");
}
else if (flag == 2) {
document.write("Prime<br>");
}
}
}
}
// Driver code
// Entered number should be greater
// than 300 to avoid Convergence of
// second factor to 1
prime(8179);
prime(7894561);
prime(90000000);
prime(841);
prime(22553);
prime(1187);
// This code is contributed by 29AjayKumar
</script>
Producción:
Prime Semi-Prime Not Prime Semi-Prime Semi-Prime Prime
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por rushiljhaveri y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA