Dado un número N, la tarea es verificar si el número dado es Proth Prime o no.
Un primo de Proth es un número de Proth que es primo.
Los primeros números primos de Proth son:
3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, …..
Ejemplos:
Input: 41 Output: 41 is Proth Prime Input: 19 Output: 19 is not a Proth Prime
Planteamiento:
La idea es encontrar números primos hasta N usando la Tamiz de Eratóstenes . Luego verifique si el número dado es Proth Number o no. Si el número es un Número Proth y también es un número primo, entonces el número dado es Proth Prime.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; int prime[1000000]; // Calculate all primes upto n. void SieveOfEratosthenes(int n) { // Initialize all entries it as true. // A value in prime[i] will finally // false if i is Not a prime, else true. for (int i = 1; i <= n + 1; i++) prime[i] = true; prime[1] = false; 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 numbers // which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } } // Utility function to check power of two bool isPowerOfTwo(int n) { return (n && !(n & (n - 1))); } // Function to check if the Given // number is Proth number or not bool isProthNumber(int n) { int k = 1; while (k < (n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(n / k)) return true; } // update k to next odd number k = k + 2; } // If we reach here means there // exists no value of K such // that k is odd number and n/k // is a power of 2 greater than k return false; } // Function to check whether the given // number is Proth Prime or Not. bool isProthPrime(int n) { // Check n for Proth Number if (isProthNumber(n - 1)) { // if number is prime, return true if (prime[n]) return true; else return false; } else return false; } // Driver Code int main() { int n = 41; // if number is proth number, // calculate primes upto n SieveOfEratosthenes(n); for (int i = 1; i <= n; i++) // Check n for Proth Prime if (isProthPrime(i)) cout << i << endl; return 0; }
Java
// Java implementation of the above approach import java.util.*; class GFG { static boolean[] prime = new boolean[1000000]; // Calculate all primes upto n. static void SieveOfEratosthenes(int n) { // Initialize all entries it as true. // A value in prime[i] will finally // false if i is Not a prime, else true. for (int i = 1; i <= n + 1; i++) prime[i] = true; prime[1] = false; 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 numbers // which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } } // Utility function to check power of two static boolean isPowerOfTwo(int n) { return (n > 0 && (n & (n - 1)) == 0); } // Function to check if the Given // number is Proth number or not static boolean isProthNumber(int n) { int k = 1; while (k < (int)(n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo((int)(n / k))) return true; } // update k to next odd number k = k + 2; } // If we reach here means there // exists no value of K such // that k is odd number and n/k // is a power of 2 greater than k return false; } // Function to check whether the given // number is Proth Prime or Not. static boolean isProthPrime(int n) { // Check n for Proth Number if (isProthNumber(n - 1)) { // if number is prime, return true if (prime[n]) return true; else return false; } else return false; } // Driver Code public static void main(String args[]) { int n = 41; // if number is proth number, // calculate primes upto n SieveOfEratosthenes(n); for (int i = 1; i <= n; i++) // Check n for Proth Prime if (isProthPrime(i)) System.out.println(i); } } // This code is contributed by // Surendra_Gangwar
Python3
# Python3 implementation of the # above approach import math as mt prime = [0 for i in range(1000000)] # Calculate all primes upto n. def SieveOfEratosthenes(n): # Initialize all entries it as true. # A value in prime[i] will finally # false if i is Not a prime, else true. for i in range(1, n + 2): prime[i] = True prime[1] = False for p in range(2, mt.ceil(n**(0.5))): # 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 numbers # which are multiple of p and are # less than p^2 are already been marked. for i in range(p * p, n + 1, p): prime[i] = False # Utility function to check power of two def isPowerOfTwo(n): return (n and (n & (n - 1)) == False) # Function to check if the Given # number is Proth number or not def isProthNumber(n): k = 1 while (k < (n // k)): # check if k divides n or not if (n % k == 0): # Check if n/k is power of 2 or not if (isPowerOfTwo(n // k)): return True # update k to next odd number k = k + 2 # If we reach here means there # exists no value of K such # that k is odd number and n/k # is a power of 2 greater than k return False # Function to check whether the given # number is Proth Prime or Not. def isProthPrime(n): # Check n for Proth Number if (isProthNumber(n - 1)): # if number is prime, return true if (prime[n]): return True else: return False else: return False # Driver Code n = 41 # if number is proth number, # calculate primes upto n SieveOfEratosthenes(n) for i in range(1, n + 1): # Check n for Proth Prime if isProthPrime(i) == True: print(i) # This code is contributed by # Mohit kumar 29
C#
// C# implementation of the above approach using System; class GFG { static Boolean[] prime = new Boolean[1000000]; // Calculate all primes upto n. static void SieveOfEratosthenes(int n) { // Initialize all entries it as true. // A value in prime[i] will finally // false if i is Not a prime, else true. for (int i = 1; i <= n + 1; i++) prime[i] = true; prime[1] = false; 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 numbers // which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } } // Utility function to check power of two static Boolean isPowerOfTwo(int n) { return (n > 0 && (n & (n - 1)) == 0); } // Function to check if the Given // number is Proth number or not static Boolean isProthNumber(int n) { int k = 1; while (k < (int)(n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo((int)(n / k))) return true; } // update k to next odd number k = k + 2; } // If we reach here means there // exists no value of K such // that k is odd number and n/k // is a power of 2 greater than k return false; } // Function to check whether the given // number is Proth Prime or Not. static Boolean isProthPrime(int n) { // Check n for Proth Number if (isProthNumber(n - 1)) { // if number is prime, return true if (prime[n]) return true; else return false; } else return false; } // Driver Code static public void Main(String []args) { int n = 41; // if number is proth number, // calculate primes upto n SieveOfEratosthenes(n); for (int i = 1; i <= n; i++) // Check n for Proth Prime if (isProthPrime(i)) Console.WriteLine(i); } } // This code is contributed by Arnab Kundu
PHP
<?php // PHP implementation of the above approach $GLOBALS['prime'] = array(); // Calculate all primes upto n. function SieveOfEratosthenes($n) { // Initialize all entries it as true. // A value in prime[i] will finally // false if i is Not a prime, else true. for ($i = 1; $i <= $n + 1; $i++) $GLOBALS['prime'][$i] = true; $GLOBALS['prime'][1] = false; for ($p = 2; $p * $p <= $n; $p++) { // If prime[p] is not changed, // then it is a prime if ($GLOBALS['prime'][$p] == true) { // Update all multiples of p greater // than or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ($i = $p * $p; $i <= $n; $i += $p) $GLOBALS['prime'][$i] = false; } } } // Utility function to check power of two function isPowerOfTwo($n) { return ($n && !($n & ($n - 1))); } // Function to check if the Given // number is Proth number or not function isProthNumber($n) { $k = 1; while ($k < ($n / $k)) { // check if k divides n or not if ($n % $k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo($n / $k)) return true; } // update k to next odd number $k = $k + 2; } // If we reach here means there // exists no value of K such // that k is odd number and n/k // is a power of 2 greater than k return false; } // Function to check whether the given // number is Proth Prime or Not. function isProthPrime($n) { // Check n for Proth Number if (isProthNumber($n - 1)) { // if number is prime, return true if ($GLOBALS['prime'][$n]) return true; else return false; } else return false; } // Driver Code $n = 41; // if number is proth number, // calculate primes upto n SieveOfEratosthenes($n); for ($i = 1; $i <= $n; $i++) // Check n for Proth Prime if (isProthPrime($i) == true) echo $i, "\n"; // This code is contributed by Ryuga ?>
Javascript
<script> // Javascript implementation of the above approach let prime = new Array(); // Calculate all primes upto n. function SieveOfEratosthenes(n) { // Initialize all entries it as true. // A value in prime[i] will finally // false if i is Not a prime, else true. for (let i = 1; i <= n + 1; i++) prime[i] = true; prime[1] = false; 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 greater // than or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i <= n; i += p) prime[i] = false; } } } // Utility function to check power of two function isPowerOfTwo(n) { return (n && !(n & (n - 1))); } // Function to check if the Given // number is Proth number or not function isProthNumber(n) { let k = 1; while (k < (n / k)) { // check if k divides n or not if (n % k == 0) { // Check if n/k is power of 2 or not if (isPowerOfTwo(n / k)) return true; } // update k to next odd number k = k + 2; } // If we reach here means there // exists no value of K such // that k is odd number and n/k // is a power of 2 greater than k return false; } // Function to check whether the given // number is Proth Prime or Not. function isProthPrime(n) { // Check n for Proth Number if (isProthNumber(n - 1)) { // if number is prime, return true if (prime[n]) return true; else return false; } else return false; } // Driver Code let n = 41; // if number is proth number, // calculate primes upto n SieveOfEratosthenes(n); for (let i = 1; i <= n; i++) // Check n for Proth Prime if (isProthPrime(i) == true) document.write(i + "<br>"); // This code is contributed by gfgking </script>
3 5 13 17 41
Complejidad de tiempo: O(n*log(log(n)))
Referencias:
- https://en.wikipedia.org/wiki/Proth_number#Proth_primes
- https://www.geeksforgeeks.org/programa-para-comprobar-si-un-número-es-proth-number-or-not/
Publicación traducida automáticamente
Artículo escrito por Rahul Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA