Legendre's Conjecture: Concept, Algorithm, Implementation in C++

Legendre's Conjecture is a statement that one prime number always exists between two natural numbers' squares, which are consecutive to each other. In this article, we will discuss Legendre's Conjecture with its algorithm and its implementation.

Mathematical statement:

There is a prime number p existing between any two numbers, i.e., n2^2 and (n+1)2^2. In this case, n is a whole number. A conjecture is a finding of a conclusion that doesn't have any mathematical proof. For this reason, Legendre's Conjecture requires no mathematical evidence.

Problem Statement:

For a given number n, where we will print each prime between the range of numbers from n^2 to (n+1)^2 from 1 to n.

Approach:

• First, create a count as a variable to keep track of the list of primes.
• Start a cycle for(i=1;i<n;i++).
• After that, repeat the top loop from j = i^2 to j = (i+1)^2.
• For every j, check if it's a prime by dividing it by numbers from 2 to the square root of j.
• If j is a prime number, increment the value in the count.
• Print count for i.

Example 1:

Let us take an example to illustrate the Legendre's Conjecture in C++.

Filename: Legendre's.cpp

Output:

 
The Value of the number m: 5
For i: 1 Total prime numbers in the following range 1 and 4 = 2
For i: 2 Total prime numbers in the following range 4 and 9 = 2
For i: 3 Total prime numbers in the following range 9 and 16 = 2
For i: 4 Total prime numbers in the following range 16 and 25 = 3
For i: 5 Total prime numbers in the following range 25 and 36 = 2
For i: 6 Total prime numbers in the following range 36 and 49 = 4
For i: 7 Total prime numbers in the following range 49 and 64 = 3
For i: 8 Total prime numbers in the following range 64 and 81 = 4   

Explanation:

• The code explains Legendre's conjecture, a number theorem hypothesis.
• It consists of three functions: key, legendre_notion, and principal. The primary function finds the prime number, m, with factors from 2 to the square root of m. After that, it returns whether m is prime or not. Significantly, usually, it assigns 1 to the role of a nonprime.
• The function called legendre_concept receives integer i and performs iteration from 1 to i. Each iteration makes two operations: i^2 and (i+1)^2. The algorithm computes how many primes are there between two squares by calling the prime function. The count is stored in the total variable and the result is printed to the console.
• The main function consists of an m=8 initialization. This m value is passed as an argument to the legendre_concept function, and then the value of m is printed to the console.
• On execution of the code, the result of the prime numbers between squares of consecutive integers from 1 to 8 is displayed.

Example 2: Efficient Approach

Let us take another example to illustrate the Legendre's Conjecture in C++

Filename: Legendre's2.cpp

Output:

 
The Value of the number is:  10
For i: 1 Total primes in the range 1 and 4 = 2
For i: 2 Total primes in the range 4 and 9 = 2
For i: 3 Total primes in the range 9 and 16 = 2
For i: 4 Total primes in the range 16 and 25 = 3
For i: 5 Total primes in the range 25 and 36 = 2
For i: 6 Total primes in the range 36 and 49 = 4
For i: 7 Total primes in the range 49 and 64 = 3
For i: 8 Total primes in the range 64 and 81 = 4
For i: 9 Total primes in the range 81 and 100 = 3
For i: 10 Total primes in the range 100 and 121 = 5   

Explanation:

• The code begins by importing the required header files and declaring a constant number 'size' to constrain the search range of the prime number, which is 10001.
• It is the function 'findPrimes' that finds all prime numbers up to 'size' by using the sieve of the Eratosthenes algorithm. It classifies multiples of each prime to be non-prime and maintains the count of non-prime numbers in the vector 'primes'.
• In the main function, the function 'findPrimes' is called to fill up the 'primes' vector with the prime count.
• After that, the loop runs from 1 to 'num', and for each iteration, 'init' and 'last' range values are calculated as ii and (i+i+1).
• The operation 'countPrimesInRange' is called to determine the number of primes within this range.

Conclusion:

In conclusion, Legendre's conjecture is an exciting mathematical conjecture that states that at least one prime number exists between consecutive squares of the natural numbers. Each experiment serves as practical proof to the hypothetical by simply determining the prime number of integers within these numbers' squares ranges.

The implementation, which the Sieve of Eratosthenes optimizes, substantially speeds up the naive strategy for values of num having a larger magnitude. Although Legendre's Conjecture has yet to be proven, the development of implementations provides practical tools to verify it within the available computational constraints.