Legendre’s Conjecture

0 0 4 minutes read

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 range $n^2$ to $(n + 1)^2$ where n is any natural number.
for examples-
2 and 3 are the primes in the range $1^2$ to $2^2$ .
5 and 7 are the primes in the range $2^2$ to $3^2$ .
11 and 13 are the primes in the range $3^2$ to $4^2$ .
17 and 19 are the primes in the range $4^2$ to $5^2$ .

Examples:

Input : 4 
output: Primes in the range 16 and 25 are:
        17
        19
        23

Explanation: Here 4² = 16 and 5² = 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 = 50
LegendreConjecture(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(n²). 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 n² and ends at
(n+1)² so, (n+1)² – n² = 2n+1.

Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!