Dado un entero positivo N, verifique si es Quartan prime o no. Escriba ‘Sí’ si es un número primo de Cuarta; de lo contrario, escriba ‘No’.
Quartan Prime : Un número primo de la forma x 4 + y 4 donde x > 0, y > 0, y xey son números enteros es un Quartan Prime.
Quartan Prime en el rango 1 – 100 son:
2, 17, 97
Ejemplos :
Input : 17 Output : Yes Explanation : 17 is a prime number and can be expressed in the form of: x4 + y4 as ( 14 + 24 ) Input : 31 Output : No Explanation: 31 is prime number but can not be expressed in the form of x4 + y4.
Una solución simple es verificar si el número dado es primo o no y luego verificar si se puede expresar en la forma de x 4 + y 4 o no.
Una solución eficiente se basa en el hecho de que cada Quartan Prime también se puede expresar en la forma 16*n + 1 . Entonces, podemos verificar si un número es primo o no y puede expresarse en la forma de 16*n + 1 o no. En caso afirmativo, entonces el número es Quartan Prime, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to check if a number is
// Quartan Prime or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number
// is prime or not
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// Driver Program
int main()
{
int n = 17;
// Check if number is prime
// and of the form 16*n + 1
if (isPrime(n) && (n % 16 == 1)) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}
Java
// JAVA program to check if a number is
// Quartan Prime or not
class GFG {
// Function to check if a number
// is prime or not
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// Driver Program
public static void main(String[] args)
{
int n = 17;
// Check if number is prime
// and of the form 16*n + 1
if (isPrime(n) && (n % 16 == 1)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
Python3
# Python 3 program to check if a number is
# Quartan Prime or not
# Utility function to check
# if a number is prime or not
def isPrime(n) :
# Corner cases
if (n <= 1) :
return False
if (n <= 3) :
return True
# This is checked so that we can skip
# middle five numbers in below loop
if (n % 2 == 0 or n % 3 == 0) :
return False
i = 5
while(i * i <= n) :
if (n % i == 0 or n % (i + 2) == 0) :
return False
i = i + 6
return True
# Driver Code
n = 17
# Check if number is prime
# and of the form 16 * n + 1
if(isPrime(n) and (n % 16 == 1) ):
print("YES")
else:
print("NO")
C#
// C# program to check if a number
// is Quartan Prime or not
using System;
class GFG
{
// Function to check if a number
// is prime or not
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we
// can skip middle five numbers
// in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
{
if (n % i == 0 || n % (i + 2) == 0)
{
return false;
}
}
return true;
}
// Driver Code
public static void Main()
{
int n = 17;
// Check if number is prime
// and of the form 16*n + 1
if (isPrime(n) && (n % 16 == 1))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed
// by inder_verma
PHP
<?php
// PHP program to check if a number
// is Quartan Prime or not
// Function to check if a
// number is prime or not
function isPrime($n)
{
// Corner cases
if ($n <= 1)
return false;
if ($n <= 3)
return true;
// This is checked so that
// we can skip middle five
// numbers in below loop
if ($n % 2 == 0 || $n % 3 == 0)
return false;
for ($i = 5; $i * $i <= $n;
$i = $i + 6)
{
if ($n % $i == 0 ||
$n % ($i + 2) == 0)
{
return false;
}
}
return true;
}
// Driver Code
$n = 17;
// Check if number is prime
// and of the form 16*n + 1
if (isPrime($n) && ($n % 16 == 1))
{
echo "YES";
}
else
{
echo "NO";
}
// This code is contributed
// anuj_67
?>
Javascript
<script>
// Javascript program to check if a number is
// Quartan Prime or not
// Function to check if a number
// is prime or not
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (var i = 5; i * i <= n; i = i + 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
// Driver Program
var n = 17;
// Check if number is prime
// and of the form 16*n + 1
if (isPrime(n) && (n % 16 == 1)) {
document.write( "YES");
}
else {
document.write( "NO");
}
// This code is contributed by itsok.
</script>
Producción:
YES