Given two integers L and R, the task is to find the number of prime numbers in the range [L, R] that can be represented by the sum of two squares of two numbers.
Examples:
Input: L = 1, R = 5
Output: 1
Explanation:
Only prime number that can be expressed as sum of two perfect squares in the given range is 5 (22 + 12)
Input: L = 7, R = 42
Output: 5
Explanation:
The prime numbers in the given range that can be expressed as sum of two perfect squares are:
13 = 22 + 32
17 = 12 + 42
29 = 52 + 22
37 = 12 + 62
41 = 52 + 42
Approach:
The given problem can be solved using Fermat’s Little theorem, which states that a prime number p can be expressed as the sum of two squares if p satisfies the following equation:
(p – 1) % 4 == 0
Follow the steps below to solve the problem:
- Traverse the range [L, R].
- For every number, check if it is a prime number of not.
- If found to be so, check if the prime number is of the form 4K + 1. If sp, increase count.
- After traversing the complete range, print count.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a prime number// satisfies the condition to be// expressed as sum of two perfect squaresbool sumSquare(int p){ return (p - 1) % 4 == 0;}// Function to check if a// number is prime or notbool isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; 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;}// Function to return the count of primes// in the range which can be expressed as// the sum of two squaresint countOfPrimes(int L, int R){ int count = 0; for (int i = L; i <= R; i++) { // If i is a prime if (isPrime(i)) { // If i can be expressed // as the sum of two squares if (sumSquare(i)) count++; } } // Return the count return count;}// Driver Codeint main(){ int L = 5, R = 41; cout << countOfPrimes(L, R);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to check if a prime number// satisfies the condition to be // expressed as sum of two perfect// squaresstatic boolean sumSquare(int p){ return (p - 1) % 4 == 0;}// Function to check if a// number is prime or notstatic boolean isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; 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;}// Function to return the count of primes// in the range which can be expressed as// the sum of two squaresstatic int countOfPrimes(int L, int R){ int count = 0; for(int i = L; i <= R; i++) { // If i is a prime if (isPrime(i)) { // If i can be expressed // as the sum of two squares if (sumSquare(i)) count++; } } // Return the count return count;}// Driver codepublic static void main(String[] args){ int L = 5, R = 41; System.out.println(countOfPrimes(L, R));}}// This code is contributed by offbeat |
Python3
# Python3 program for the# above approach# Function to check if a prime number# satisfies the condition to be # expressed as sum of two perfect# squares def sumsquare(p): return (p - 1) % 4 == 0# 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 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 += 6 return True# Function to return the count of primes # in the range which can be expressed as # the sum of two squares def countOfPrimes(L, R): count = 0 for i in range(L, R + 1): # If i is a prime if (isprime(i)): # If i can be expressed # as the sum of two squares if sumsquare(i): count += 1 # Return the count return count# Driver codeif __name__=='__main__': L = 5 R = 41 print(countOfPrimes(L, R)) # This code is contributed by virusbuddah_ |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to check if a prime number// satisfies the condition to be // expressed as sum of two perfect// squaresstatic bool sumSquare(int p){ return (p - 1) % 4 == 0;}// Function to check if a// number is prime or notstatic bool isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; 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;}// Function to return the count of primes// in the range which can be expressed as// the sum of two squaresstatic int countOfPrimes(int L, int R){ int count = 0; for(int i = L; i <= R; i++) { // If i is a prime if (isPrime(i)) { // If i can be expressed // as the sum of two squares if (sumSquare(i)) count++; } } // Return the count return count;}// Driver codepublic static void Main(String[] args){ int L = 5, R = 41; Console.WriteLine(countOfPrimes(L, R));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to implement// the above approach // Function to check if a prime number // satisfies the condition to be // expressed as sum of two perfect // squares function sumSquare(p) { return (p - 1) % 4 == 0; } // 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; 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; } // Function to return the count of primes // in the range which can be expressed as // the sum of two squares function countOfPrimes(L , R) { var count = 0; for (var i = L; i <= R; i++) { // If i is a prime if (isPrime(i)) { // If i can be expressed // as the sum of two squares if (sumSquare(i)) count++; } } // Return the count return count; } // Driver code var L = 5, R = 41; document.write(countOfPrimes(L, R));// This code is contributed by todaysgaurav </script> |
Output:
6
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
