Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explained Legendre's conjecture, presented an implementation of an Algorithm to verify Legendre's conjecture till a given limit and have provided output which you can analyze.
Table of contents:
- Legendre's conjecture
- Example of Legendre's conjecture
- Implementation of Legendre's conjecture in C++
- Time and Space Complexity analysis
- Output from 1 to 10404
Legendre's conjecture
Legendre's conjecture founded and proposed by Adrien-Marie Legendre states that there always exist a prime number pr that lies between i^2 and (i+1)^2 where i is a positive integer.
If we have a positive integer i=1 so our range becomes 1 to 4 as (1+1)^2=4 so from 1 to 4 there are two prime numbers 2 and 3. Now if we take i as 2 we have range from 4 to 9 and in this range there are two prime numbers 5 and 7. If we take i as 4 so range becomes 16 to 25 and there are 3 prime numbers in this range 17,19 and 23. We can see that indeed, the Legendre Conjecture holds true for the cases considered, with at least two prime numbers, pr, fulfilling the inequality, i^2 < pr < (i+1)^2.
If we see further, the positive integers, i^2 and (i+1)^2 are referred to as square numbers. But, how can a person prove conjecture true for any integer? The best proof was given by Chinese mathematician, Chen Jingrun who has given a slightly weaker or lower version of Legendre’s Conjecture: there is either a prime, p in the interval, i^2 < pr < (i+1)^2 or a semiprime, pq, in the interval, i^2 < pq < (i+1)^2, where q is a prime not equal to pr. The proper proof and approval was not given to legendre's conjecture till now so it somehow becomes a part of debate of how to prove this. Conjecture in legendre's conjecture signifies that this theorem is not proved and approved till now as conjecture means any thing that is not proven and that's why the name legendre's conjecture.
Now after getting some knowledge regarding legendre's conjecture we would directly dive into solving our problem or writing an algorithm or code for this. The given problem says that we have to find prime numbers in the given range in between i^2 and (i+1)^2 and vary i from 1 to inputted number. First let's see an example of what we have to do in this particular problem.
Example of Legendre's conjecture
Suppose we have a input number n=4 so we have to traverse from 1 to 4 and for each iteration we have to print number of primes in the range i^2 and (i+1)^2 where i is ranging from 1 to 4.
for i=1 we have range from 1 to 4 and total primes are two i.e, 2 and 3.
for i=2 we have range from 4 to 9 and total primes are two i.e, 5 and 7.
for i=3 we have range from 9 to 16 and total primes are two i.e, 11 and 13.
for i=4 we have range from 16 to 25 and total primes are three i.e, 17,19 and 23.
So for each iteration we have to print the count of prime numbers. So our output would look like:
Output:
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
Implementation of Legendre's conjecture in C++
Now let's understand how to approach this problem. First we will create a function to check whether a number is prime or not and after checking that we simply apply loops and for each iteration we keep on counting prime in the range and printing that.
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
//function for checking prime number
bool isprime(int n)
{
if(n==1){
return false;
}
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
//function for printing number of primes
void legendre(int n){
for(int i=1;i<=n;i++){
int cnt=0; //variable for storing count of prime numbers
for(int j=i*i;j<=((i+1)*(i+1));j++){
if(isprime(j)){
cnt++;
}
}
cout<<"For i = "<<i<<" "<<"Total primes in the range"<<" "<<(i*i)<<" "<<"and"<<" "<<(i+1)*(i+1)<<" "<<"="<<" "<<cnt<<'\n';
}
}
int main(void){
int n;
cout<<"Enter a number:"<<'\n';
cin>>n;
legendre(n);
}
Output:
Enter a number:
4
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
Time and Space Complexity analysis
This algorithm will take O(n^2) time complexity as nested loops are required. So we can say that this algorithm works for small integer but for large integers it is not efficient enough.
We will see another approach in which we will be using a technique known as sieve method also called as sieve of eratosthenes. This method help us to find prime numbers in less time as compared to normal brute force method. In this method we will count prime numbers using sieve method by taking a boolean array and then counting prime numbers in a range i^2 and (i+1)^2.
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
const int size = 10000;
//cnt[i] will store count of primes
int cnt[size + 1];
void primeCont()
{
bool pr[size + 1];
memset(pr, true, sizeof(pr));
for (int i = 2; i * i <= size; i++) {
if (pr[i] == true) {
for (int j = i * 2; j <= size; j += i)
pr[j] = false;
}
}
cnt[0] = 0;
cnt[1] = 0;
for (int i = 2; i <= size; i++) {
cnt[i] = cnt[i - 1];
if (pr[i])
cnt[i]++;
}
}
//function to find total primes in range
int totalPrime(int start, int end)
{
return cnt[end] - cnt[start - 1];
}
int main(void)
{
primeCont();
int n;
cout<<"Enter a number:"<<'\n';
cin>>n;
int start,end;
for(int i=1;i<=n;i++){
start=i*i;
end=(i+1)*(i+1);
cout<<"For i = "<<" "<<i<<" "<<"Total primes in the range"<<" "<<start<<" "<<"and"<<" "<<end<<" "<<"="<<" "<<totalPrime(start,end)<<'\n';
}
return 0;
}
Output:
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
This method is somehow more efficient as compared to above explained so that's why we prefer using this method only.
Output from 1 to 10404
Following is the number of primes between i2 and (i+1)2 for i from 1 to 101:
Enter a number:
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
For i = 11 Total primes in the range 121 and 144 = 4
For i = 12 Total primes in the range 144 and 169 = 5
For i = 13 Total primes in the range 169 and 196 = 5
For i = 14 Total primes in the range 196 and 225 = 4
For i = 15 Total primes in the range 225 and 256 = 6
For i = 16 Total primes in the range 256 and 289 = 7
For i = 17 Total primes in the range 289 and 324 = 5
For i = 18 Total primes in the range 324 and 361 = 6
For i = 19 Total primes in the range 361 and 400 = 6
For i = 20 Total primes in the range 400 and 441 = 7
For i = 21 Total primes in the range 441 and 484 = 7
For i = 22 Total primes in the range 484 and 529 = 7
For i = 23 Total primes in the range 529 and 576 = 6
For i = 24 Total primes in the range 576 and 625 = 9
For i = 25 Total primes in the range 625 and 676 = 8
For i = 26 Total primes in the range 676 and 729 = 7
For i = 27 Total primes in the range 729 and 784 = 8
For i = 28 Total primes in the range 784 and 841 = 9
For i = 29 Total primes in the range 841 and 900 = 8
For i = 30 Total primes in the range 900 and 961 = 8
For i = 31 Total primes in the range 961 and 1024 = 10
For i = 32 Total primes in the range 1024 and 1089 = 9
For i = 33 Total primes in the range 1089 and 1156 = 10
For i = 34 Total primes in the range 1156 and 1225 = 9
For i = 35 Total primes in the range 1225 and 1296 = 10
For i = 36 Total primes in the range 1296 and 1369 = 9
For i = 37 Total primes in the range 1369 and 1444 = 9
For i = 38 Total primes in the range 1444 and 1521 = 12
For i = 39 Total primes in the range 1521 and 1600 = 11
For i = 40 Total primes in the range 1600 and 1681 = 12
For i = 41 Total primes in the range 1681 and 1764 = 11
For i = 42 Total primes in the range 1764 and 1849 = 9
For i = 43 Total primes in the range 1849 and 1936 = 12
For i = 44 Total primes in the range 1936 and 2025 = 11
For i = 45 Total primes in the range 2025 and 2116 = 13
For i = 46 Total primes in the range 2116 and 2209 = 10
For i = 47 Total primes in the range 2209 and 2304 = 13
For i = 48 Total primes in the range 2304 and 2401 = 15
For i = 49 Total primes in the range 2401 and 2500 = 10
For i = 50 Total primes in the range 2500 and 2601 = 11
For i = 51 Total primes in the range 2601 and 2704 = 15
For i = 52 Total primes in the range 2704 and 2809 = 16
For i = 53 Total primes in the range 2809 and 2916 = 12
For i = 54 Total primes in the range 2916 and 3025 = 13
For i = 55 Total primes in the range 3025 and 3136 = 11
For i = 56 Total primes in the range 3136 and 3249 = 12
For i = 57 Total primes in the range 3249 and 3364 = 17
For i = 58 Total primes in the range 3364 and 3481 = 13
For i = 59 Total primes in the range 3481 and 3600 = 16
For i = 60 Total primes in the range 3600 and 3721 = 16
For i = 61 Total primes in the range 3721 and 3844 = 13
For i = 62 Total primes in the range 3844 and 3969 = 17
For i = 63 Total primes in the range 3969 and 4096 = 15
For i = 64 Total primes in the range 4096 and 4225 = 14
For i = 65 Total primes in the range 4225 and 4356 = 16
For i = 66 Total primes in the range 4356 and 4489 = 15
For i = 67 Total primes in the range 4489 and 4624 = 15
For i = 68 Total primes in the range 4624 and 4761 = 17
For i = 69 Total primes in the range 4761 and 4900 = 13
For i = 70 Total primes in the range 4900 and 5041 = 21
For i = 71 Total primes in the range 5041 and 5184 = 15
For i = 72 Total primes in the range 5184 and 5329 = 15
For i = 73 Total primes in the range 5329 and 5476 = 17
For i = 74 Total primes in the range 5476 and 5625 = 17
For i = 75 Total primes in the range 5625 and 5776 = 18
For i = 76 Total primes in the range 5776 and 5929 = 22
For i = 77 Total primes in the range 5929 and 6084 = 14
For i = 78 Total primes in the range 6084 and 6241 = 18
For i = 79 Total primes in the range 6241 and 6400 = 23
For i = 80 Total primes in the range 6400 and 6561 = 13
For i = 81 Total primes in the range 6561 and 6724 = 20
For i = 82 Total primes in the range 6724 and 6889 = 19
For i = 83 Total primes in the range 6889 and 7056 = 20
For i = 84 Total primes in the range 7056 and 7225 = 17
For i = 85 Total primes in the range 7225 and 7396 = 16
For i = 86 Total primes in the range 7396 and 7569 = 21
For i = 87 Total primes in the range 7569 and 7744 = 22
For i = 88 Total primes in the range 7744 and 7921 = 18
For i = 89 Total primes in the range 7921 and 8100 = 18
For i = 90 Total primes in the range 8100 and 8281 = 20
For i = 91 Total primes in the range 8281 and 8464 = 20
For i = 92 Total primes in the range 8464 and 8649 = 19
For i = 93 Total primes in the range 8649 and 8836 = 23
For i = 94 Total primes in the range 8836 and 9025 = 21
For i = 95 Total primes in the range 9025 and 9216 = 21
For i = 96 Total primes in the range 9216 and 9409 = 21
For i = 97 Total primes in the range 9409 and 9604 = 22
For i = 98 Total primes in the range 9604 and 9801 = 23
For i = 99 Total primes in the range 9801 and 10000 = 21
For i = 100 Total primes in the range 10000 and 10201 = 23
For i = 101 Total primes in the range 10201 and 10404 = 22
From the above sample output, you can see that the number of primes
So now we have seen about this algorithm and I hope you all will definitely try this problem by yourself atleast once. Legendre's conjecture is not proven yet but we have seen a little overview of how this works and what is the idea behind this. Hope you like it. With this article at OpenGenus, you must have the complete idea of Legendre's conjecture.
Happy coding.
Thank you.
