It says that there is always one prime number between any two consecutive natural number’s(n = 1, 2, 3, 4, 5, …) square. This is called Legendre’s Conjecture.
Conjecture: A conjecture is a proposition or conclusion based upon incomplete information to which no proof has been found i.e it has not been proved or disproved.
Mathematically,
there is always one prime p in the rangeto
where n is any natural number.
for examples-
2 and 3 are the primes in the rangeto
.
5 and 7 are the primes in the range
11 and 13 are the primes in the range.
17 and 19 are the primes in the range
to 
where n is any natural number.
to 
.
.
.
.Examples:
Input : 4
output: Primes in the range 16 and 25 are:
17
19
23
Explanation: Here 42 = 16 and 52 = 25
Hence, prime numbers between 16 and 25 are 17, 19 and 23.
Input : 10
Output: Primes in the range 100 and 121 are:
101
103
107
109
113
C++
// C++ program to verify Legendre's Conjecture // for a given n. #include <bits/stdc++.h> using namespace std; // prime checking bool isprime(int n) { for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } void LegendreConjecture(int n) { cout << "Primes in the range "<<n*n << " and "<<(n+1)*(n+1) <<" are:" <<endl; for (int i = n*n; i <= ((n+1)*(n+1)); i++) // searching for primes if (isprime(i)) cout << i <<endl; } // Driver program int main() { int n = 50; LegendreConjecture(n); return 0; } |
Java
// Java program to verify Legendre's Conjecture // for a given n. class GFG { // prime checking static boolean isprime(int n) { for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } static void LegendreConjecture(int n) { System.out.println("Primes in the range "+n*n +" and "+(n+1)*(n+1) +" are:"); for (int i = n*n; i <= ((n+1)*(n+1)); i++) { // searching for primes if (isprime(i)) System.out.println(i); } } // Driver program public static void main(String[] args) { int n = 50; LegendreConjecture(n); } } //This code is contributed by //Smitha Dinesh Semwal |
Python3
# Python3 program to verify Legendre's Conjecture # for a given n import math def isprime( n ): i = 2 for i in range (2, int((math.sqrt(n)+1))): if n%i == 0: return False return True def LegendreConjecture( n ): print ( "Primes in the range ", n*n , " and ", (n+1)*(n+1) , " are:" ) for i in range (n*n, (((n+1)*(n+1))+1)): if(isprime(i)): print (i) n = 50LegendreConjecture(n) # Contributed by _omg |
C#
// C# program to verify Legendre's // Conjecture for a given n. using System; class GFG { // prime checking static Boolean isprime(int n) { for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } static void LegendreConjecture(int n) { Console.WriteLine("Primes in the range " + n * n + " and " + (n + 1) * (n + 1) + " are:"); for (int i = n * n; i <= ((n + 1) * (n + 1)); i++) { // searching for primes if (isprime(i)) Console.WriteLine(i); } } // Driver program public static void Main(String[] args) { int n = 50; LegendreConjecture(n); } } // This code is contributed by parashar. |
PHP
<?php // PHP program to verify // Legendre's Conjecture // for a given n. // prime checking function isprime($n) { for ($i = 2; $i * $i <= $n; $i++) if ($n % $i == 0) return false; return true; } function LegendreConjecture($n) { echo "Primes in the range ",$n* $n, " and ",($n + 1) * ($n + 1), " are:\n" ; for ($i = $n * $n; $i <= (($n + 1) * ($n + 1)); $i++) // searching for primes if (isprime($i)) echo $i ,"\n"; } // Driver Code $n = 50; LegendreConjecture($n); // This code is contributed by ajit. ?> |
Javascript
<script> // JavaScript program to verify // Legendre's Conjecture for a given n. // Prime checking function isprime(n) { for(let i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } function LegendreConjecture(n) { document.write("Primes in the range " + n * n + " and " + (n + 1) * (n + 1) + " are:" + "<br/>"); for(let i = n * n; i <= ((n + 1) * (n + 1)); i++) { // Searching for primes if (isprime(i)) document.write(i + "<br/>"); } } // Driver code let n = 50; LegendreConjecture(n); // This code is contributed by splevel62 </script> |
Output :
Primes in the range 2500 and 2601 are: 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593
Time Complexity: O(n2). isPrime() function takes O(n) time and it is embedded in LegendreConjecture() function which also takes O(n) time as it has loop which starts from n2 and ends at
(n+1)2 so, (n+1)2 – n2 = 2n+1.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
