Blum Integer es un número semiprimo , suponga que p y q son los dos factores (es decir, n = p * q), ellos (p y q) son de la forma 4t + 3, donde t es un número entero.
Los primeros enteros de Blum son 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, …
Nota: Debido a la condición de que ambos factores deben ser semiprimos, los números pares no pueden ser enteros de Blum ni los números menores de 20,
por lo que solo debemos verificar un entero impar mayor que 20 si es un entero de Blum. O no.
Ejemplos:
Input: 33 Output: Yes Explanation: 33 = 3 * 11, 3 and 11 are both semi-primes as well as of the form 4t + 3 for t = 0, 2 Input: 77 Output: Yes Explanation: 77 = 7 * 11, 7 and 11 both are semi-prime as well as of the form 4t + 3 for t = 1, 2 Input: 25 Output: No Explanation: 25 = 5*5, 5 and 5 are both semi-prime but are not of the form 4t + 3, Hence 25 is not a Blum integer.
Enfoque: Para un entero impar dado mayor que 20, calculamos los números primos desde 1 hasta ese entero impar. Si encontramos cualquier número primo que divida ese entero impar y su cociente, ambos son primos y siguen la forma 4t + 3 para algún entero, entonces el entero impar dado es Blum Integer.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if a number is a Blum
// integer
#include <bits/stdc++.h>
using namespace std;
// Function to cheek if number is Blum Integer
bool isBlumInteger(int n)
{
bool prime[n + 1];
memset(prime, true, sizeof(prime));
// to store prime numbers from 2 to n
for (int i = 2; i * i <= n; i++) {
// If prime[i] is not
// changed, then it is a prime
if (prime[i] == true) {
// Update all multiples of p
for (int j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
// to check if the given odd integer
// is Blum Integer or not
for (int i = 2; i <= n; i++) {
if (prime[i]) {
// checking the factors
// are of 4t+3 form or not
if ((n % i == 0) && ((i - 3) % 4) == 0) {
int q = n / i;
return (q != i && prime[q] &&
(q - 3) % 4 == 0);
}
}
}
return false;
}
// driver code
int main()
{
// give odd integer greater than 20
int n = 249;
if (isBlumInteger(n))
cout << "Yes";
else
cout << "No";
}
Java
// Java implementation to check If
// a number is a Blum integer
import java.util.*;
class GFG {
public static boolean isBlumInteger(int n)
{
boolean prime[] = new boolean[n + 1];
for (int i = 0; i < n; i++)
prime[i] = true;
// to store prime numbers from 2 to n
for (int i = 2; i * i <= n; i++) {
// If prime[i] is not changed,
// then it is a prime
if (prime[i] == true) {
// Update all multiples of p
for (int j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
// to check if the given odd integer
// is Blum Integer or not
for (int i = 2; i <= n; i++) {
if (prime[i]) {
// checking the factors are
// of 4t + 3 form or not
if ((n % i == 0) && ((i - 3) % 4) == 0) {
int q = n / i;
return (q != i && prime[q] &&
(q - 3) % 4 == 0);
}
}
}
return false;
}
// driver code
public static void main(String[] args)
{
// give odd integer greater than 20
int n = 249;
if (isBlumInteger(n) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# python 3 program to check if a
# number is a Blum integer
# Function to cheek if number
# is Blum Integer
def isBlumInteger(n):
prime = [True]*(n + 1)
# to store prime numbers from 2 to n
i = 2
while (i * i <= n):
# If prime[i] is not
# changed, then it is a prime
if (prime[i] == True) :
# Update all multiples of p
for j in range(i * 2, n + 1, i):
prime[j] = False
i = i + 1
# to check if the given odd integer
# is Blum Integer or not
for i in range(2, n + 1) :
if (prime[i]) :
# checking the factors
# are of 4t+3 form or not
if ((n % i == 0) and
((i - 3) % 4) == 0):
q = int(n / i)
return (q != i and prime[q]
and (q - 3) % 4 == 0)
return False
# driver code
# give odd integer greater than 20
n = 249
if (isBlumInteger(n)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha.
C#
// C# implementation to check If
// a number is a Blum integer
using System;
class GFG {
public static bool isBlumInteger(int n)
{
bool[] prime = new bool[n + 1];
for (int i = 0; i < n; i++)
prime[i] = true;
// to store prime numbers from 2 to n
for (int i = 2; i * i <= n; i++) {
// If prime[i] is not changed,
// then it is a prime
if (prime[i] == true) {
// Update all multiples of p
for (int j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
// to check if the given odd integer
// is Blum Integer or not
for (int i = 2; i <= n; i++) {
if (prime[i]) {
// checking the factors are
// of 4t + 3 form or not
if ((n % i == 0) && ((i - 3) % 4) == 0)
{
int q = n / i;
return (q != i && prime[q] &&
(q - 3) % 4 == 0);
}
}
}
return false;
}
// Driver code
static public void Main ()
{
// give odd integer greater than 20
int n = 249;
if (isBlumInteger(n) == true)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Ajit.
PHP
<?php
// PHP program to check if a
// number is a Blum integer
// Function to cheek if
// number is Blum Integer
function isBlumInteger($n)
{
$prime = array_fill(0, $n + 1, true);
// to store prime
// numbers from 2 to n
for ($i = 2; $i * $i <= $n; $i++)
{
// If prime[i] is not
// changed, then it is a prime
if ($prime[$i] == true)
{
// Update all multiples of p
for ($j = $i * 2; $j <= $n; $j += $i)
$prime[$j] = false;
}
}
// to check if the given
// odd integer is Blum
// Integer or not
for ($i = 2; $i <= $n; $i++)
{
if ($prime[$i])
{
// checking the factors
// are of 4t+3 form or not
if (($n % $i == 0) &&
(($i - 3) % 4) == 0)
{
$q = (int)$n / $i;
return ($q != $i && $prime[$q] &&
($q - 3) % 4 == 0);
}
}
}
return false;
}
// Driver code
// give odd integer
// greater than 20
$n = 249;
if (isBlumInteger($n))
echo "Yes";
else
echo "No";
// This code is contributed by mits.
?>
Javascript
<script>
// Javascript implementation to check If
// a number is a Blum integer
function isBlumInteger(n)
{
let prime = new Array(n + 1);
for(let i = 0; i < n; i++)
prime[i] = true;
// To store prime numbers from 2 to n
for(let i = 2; i * i <= n; i++)
{
// If prime[i] is not changed,
// then it is a prime
if (prime[i] == true)
{
// Update all multiples of p
for(let j = i * 2; j <= n; j += i)
prime[j] = false;
}
}
// To check if the given odd integer
// is Blum Integer or not
for(let i = 2; i <= n; i++)
{
if (prime[i])
{
// Checking the factors are
// of 4t + 3 form or not
if ((n % i == 0) && ((i - 3) % 4) == 0)
{
let q = parseInt(n / i, 10);
return (q != i && prime[q] &&
(q - 3) % 4 == 0);
}
}
}
return false;
}
// Driver code
// Give odd integer greater than 20
let n = 249;
if (isBlumInteger(n) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by decode2207
</script>
Producción:
Yes
Complejidad de Tiempo: O(nsqrtn)
Espacio Auxiliar: O(n)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.