Dado un número N , la tarea es encontrar el número de primos interesantes menores que iguales a N .
Un primo interesante es cualquier número primo que pueda escribirse como a 2 + b 4 , donde a y b son números enteros positivos. Por ejemplo, el número primo interesante más pequeño es 2 = 1 2 + 1 4 .
Ejemplos:
Entrada: N = 10
Salida: 2
2 = 1 2 + 1 4
5 = 2 2 + 1 4
Ambos son primos interesantes menores que iguales a 10Entrada: N = 1000
Salida: 28
Enfoque ingenuo:
- Iterar a través de todos los números del 1 al N .
- Para cada número, comprueba si es primo o no.
- Si es primo, comprueba si se puede representar como a 2 + b 4 mediante:
- Iterar a través de todos los valores posibles de b de 1 a N 1/4 .
- Para cada valor de b , compruebe si N – b 4 es un cuadrado perfecto o no (es decir, puede ser un 2 o no).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of interesting primes up to N
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number
// is prime or not
bool isPrime(int n)
{
int flag = 1;
// If n is divisible by any
// number between 2 and sqrt(n),
// it is not prime
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
flag = 0;
break;
}
}
return (flag == 1 ? true : false);
}
// Function to check if a number
// is perfect square or not
bool isPerfectSquare(int x)
{
// Find floating point value of
// square root of x.
long double sr = sqrt(x);
// If square root is an integer
return ((sr - floor(sr)) == 0);
}
// Function to find the number of interesting
// primes less than equal to N.
int countInterestingPrimes(int n)
{
int answer = 0;
for (int i = 2; i <= n; i++) {
// Check whether the number
// is prime or not
if (isPrime(i)) {
// Iterate for values of b
for (int j = 1;
j * j * j * j <= i;
j++) {
// Check condition for a
if (
isPerfectSquare(
i - j * j * j * j)) {
answer++;
break;
}
}
}
}
// Return the required answer
return answer;
}
// Driver code
int main()
{
int N = 10;
cout << countInterestingPrimes(N);
return 0;
}
Java
// Java program to find the number
// of interesting primes up to N
class GFG{
// Function to check if a number
// is prime or not
static boolean isPrime(int n)
{
int flag = 1;
// If n is divisible by any
// number between 2 and Math.sqrt(n),
// it is not prime
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
flag = 0;
break;
}
}
return (flag == 1 ? true : false);
}
// Function to check if a number
// is perfect square or not
static boolean isPerfectSquare(int x)
{
// Find floating point value of
// square root of x.
double sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function to find the number of interesting
// primes less than equal to N.
static int countInterestingPrimes(int n)
{
int answer = 0;
for (int i = 2; i <= n; i++) {
// Check whether the number
// is prime or not
if (isPrime(i)) {
// Iterate for values of b
for (int j = 1;
j * j * j * j <= i;
j++) {
// Check condition for a
if (
isPerfectSquare(
i - j * j * j * j)) {
answer++;
break;
}
}
}
}
// Return the required answer
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 10;
System.out.print(countInterestingPrimes(N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find the number # of interesting primes up to N import math # Function to check if a number # is prime or not def isPrime(n): flag = 1 # If n is divisible by any # number between 2 and sqrt(n), # it is not prime i = 2 while(i * i <= n): if (n % i == 0): flag = 0 break i += 1 return (True if flag == 1 else False) # Function to check if a number # is perfect square or not def isPerfectSquare(x): # Find floating povalue of # square root of x. sr = math.sqrt(x) # If square root is an integer return ((sr - math.floor(sr)) == 0) # Function to find the number of interesting # primes less than equal to N. def countInterestingPrimes(n): answer = 0 for i in range(2, n): # Check whether the number # is prime or not if (isPrime(i)): # Iterate for values of b j = 1 while(j * j * j * j <= i): # Check condition for a if (isPerfectSquare(i - j * j * j * j)): answer += 1 break j += 1 # Return the required answer return answer # Driver code if __name__=='__main__': N = 10 print(countInterestingPrimes(N)) # This code is contributed by AbhiThakur
C#
// C# program to find the number
// of interesting primes up to N
using System;
using System.Collections.Generic;
class GFG{
// Function to check if a number
// is prime or not
static bool isPrime(int n)
{
int flag = 1;
// If n is divisible by any
// number between 2 and Math.Sqrt(n),
// it is not prime
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
flag = 0;
break;
}
}
return (flag == 1 ? true : false);
}
// Function to check if a number
// is perfect square or not
static bool isPerfectSquare(int x)
{
// Find floating point value of
// square root of x.
double sr = Math.Sqrt(x);
// If square root is an integer
return ((sr - Math.Floor(sr)) == 0);
}
// Function to find the number of interesting
// primes less than equal to N.
static int countInterestingPrimes(int n)
{
int answer = 0;
for (int i = 2; i <= n; i++) {
// Check whether the number
// is prime or not
if (isPrime(i)) {
// Iterate for values of b
for (int j = 1;
j * j * j * j <= i;
j++) {
// Check condition for a
if (
isPerfectSquare(
i - j * j * j * j)) {
answer++;
break;
}
}
}
}
// Return the required answer
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 10;
Console.Write(countInterestingPrimes(N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Java script program to find the number
// of interesting primes up to N
// Function to check if a number
// is prime or not
function isPrime( n)
{
let flag = 1;
// If n is divisible by any
// number between 2 and Math.sqrt(n),
// it is not prime
for (let i = 2; i * i <= n; i++) {
if (n % i == 0) {
flag = 0;
break;
}
}
return (flag == 1 ? true : false);
}
// Function to check if a number
// is perfect square or not
function isPerfectSquare( x)
{
// Find floating point value of
// square root of x.
let sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0);
}
// Function to find the number of interesting
// primes less than equal to N.
function countInterestingPrimes( n)
{
let answer = 0;
for (let i = 2; i <= n; i++) {
// Check whether the number
// is prime or not
if (isPrime(i)) {
// Iterate for values of b
for (let j = 1;
j * j * j * j <= i;
j++) {
// Check condition for a
if (
isPerfectSquare(
i - j * j * j * j)) {
answer++;
break;
}
}
}
}
// Return the required answer
return answer;
}
// Driver code
let N = 10;
document.write(countInterestingPrimes(N));
// This code is contributed by Bobby
</script>
Producción:
2
Complejidad de tiempo : O(N)
Espacio Auxiliar: O(1)
Enfoque eficiente:
- Si almacenamos todos los cuadrados perfectos y los cuadruplicados perfectos hasta N , entonces podemos iterar a través de todos los pares y verificar si el resultado es primo o no.
- Para optimizar aún más, podemos almacenar todos los primos hasta N usando el tamiz de eratóstenes y hacer la verificación de primalidad en O(1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of interesting primes up to N.
#include <bits/stdc++.h>
using namespace std;
// Function to find all prime numbers
void SieveOfEratosthenes(
int n,
unordered_set<int>& allPrimes)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime.
bool prime[n + 1];
memset(prime, true, sizeof(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
// greater than or equal to
// the square of it
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
allPrimes.insert(p);
}
// Function to check if a number
// is perfect square or not
int countInterestingPrimes(int n)
{
// To store all primes
unordered_set<int> allPrimes;
SieveOfEratosthenes(n, allPrimes);
// To store all interseting primes
unordered_set<int> intersetingPrimes;
vector<int> squares, quadruples;
// Store all perfect squares
for (int i = 1; i * i <= n; i++) {
squares.push_back(i * i);
}
// Store all perfect quadruples
for (int i = 1; i * i * i * i <= n; i++) {
quadruples.push_back(i * i * i * i);
}
// Store all interseting primes
for (auto a : squares) {
for (auto b : quadruples) {
if (allPrimes.count(a + b))
intersetingPrimes.insert(a + b);
}
}
// Return count of interseting primes
return intersetingPrimes.size();
}
// Driver code
int main()
{
int N = 10;
cout << countInterestingPrimes(N);
return 0;
}
Java
// Java program to find the number
// of interesting primes up to N.
import java.util.*;
class GFG{
// Function to find all prime numbers
static void SieveOfEratosthenes(
int n, HashSet<Integer> allPrimes)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime.
boolean []prime = new boolean[n + 1];
Arrays.fill(prime, true);
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
// greater than or equal to
// the square of it
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
allPrimes.add(p);
}
// Function to check if a number
// is perfect square or not
static int countInterestingPrimes(int n)
{
// To store all primes
HashSet<Integer> allPrimes = new HashSet<Integer>();
SieveOfEratosthenes(n, allPrimes);
// To store all interseting primes
HashSet<Integer> intersetingPrimes = new HashSet<Integer>();
Vector<Integer> squares = new Vector<Integer>()
, quadruples = new Vector<Integer>();
// Store all perfect squares
for (int i = 1; i * i <= n; i++) {
squares.add(i * i);
}
// Store all perfect quadruples
for (int i = 1; i * i * i * i <= n; i++) {
quadruples.add(i * i * i * i);
}
// Store all interseting primes
for (int a : squares) {
for (int b : quadruples) {
if (allPrimes.contains(a + b))
intersetingPrimes.add(a + b);
}
}
// Return count of interseting primes
return intersetingPrimes.size();
}
// Driver code
public static void main(String[] args)
{
int N = 10;
System.out.print(countInterestingPrimes(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the number # of interesting primes up to N. # Function to find all prime numbers def SieveOfEratosthenes(n, allPrimes): # Create a boolean array "prime[0..n]" # and initialize all entries as true. # A value in prime[i] will finally # be false if i is Not a prime. prime = [True] * (n + 1) 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 # greater than or equal to # the square of it for i in range(p * p, n + 1, p): prime[i] = False p += 1 # Store all prime numbers for p in range(2, n + 1): if prime[p]: allPrimes.add(p) # Function to check if a number # is perfect square or not def countInterestingPrimes(n): # To store all primes allPrimes = set() # To store all interseting primes SieveOfEratosthenes(n, allPrimes) # To store all interseting primes interestingPrimes = set() squares, quadruples = [], [] # Store all perfect squares i = 1 while i * i <= n: squares.append(i * i) i += 1 # Store all perfect quadruples i = 1 while i * i * i * i <= n: quadruples.append(i * i * i * i) i += 1 # Store all interseting primes for a in squares: for b in quadruples: if a + b in allPrimes: interestingPrimes.add(a + b) # Return count of interseting primes return len(interestingPrimes) # Driver code N = 10 print(countInterestingPrimes(N)) # This code is contributed by Shivam Singh
C#
// C# program to find the number
// of interesting primes up to N.
using System;
using System.Collections.Generic;
class GFG{
// Function to find all prime numbers
static void SieveOfEratosthenes(
int n, HashSet<int> allPrimes)
{
// Create a bool array "prime[0..n]"
// and initialize all entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime.
bool []prime = new bool[n + 1];
for(int i = 0; i < n + 1; i++)
prime[i] = true;
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
// greater than or equal to
// the square of it
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
allPrimes.Add(p);
}
// Function to check if a number
// is perfect square or not
static int countInterestingPrimes(int n)
{
// To store all primes
HashSet<int> allPrimes = new HashSet<int>();
SieveOfEratosthenes(n, allPrimes);
// To store all interseting primes
HashSet<int> intersetingPrimes = new HashSet<int>();
List<int> squares = new List<int>()
, quadruples = new List<int>();
// Store all perfect squares
for (int i = 1; i * i <= n; i++) {
squares.Add(i * i);
}
// Store all perfect quadruples
for (int i = 1; i * i * i * i <= n; i++) {
quadruples.Add(i * i * i * i);
}
// Store all interseting primes
foreach (int a in squares) {
foreach (int b in quadruples) {
if (allPrimes.Contains(a + b))
intersetingPrimes.Add(a + b);
}
}
// Return count of interseting primes
return intersetingPrimes.Count;
}
// Driver code
public static void Main(String[] args)
{
int N = 10;
Console.Write(countInterestingPrimes(N));
}
}
// This code is contributed by Rajput-Ji
Producción:
2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)