Diz que há sempre um número primo entre quaisquer quadrados de dois números naturais consecutivos (n = 1, 2, 3, 4, 5, ...). Isso é chamado de conjectura de Legendre .
Conjectura: Uma conjectura é uma proposição ou conclusão baseada em informações incompletas para as quais nenhuma prova foi encontrada, ou seja, não foi provada ou refutada.

Matematicamente,
há sempre um primo p no intervalo n ^ 2até (n + 1) ^ 2onde n é qualquer número natural.

por exemplo,
2 e 3 são os primos no intervalo 1 ^ 2de 2 ^ 2.

5 e 7 são os primos no intervalo 2 ^ 2de 3 ^ 2.

11 e 13 são os primos no intervalo 3 ^ 2de 4 ^ 2.



17 e 19 são os primos no intervalo 4 ^ 2de 5 ^ 2.

Exemplos:

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

Explicação : Aqui, 4 2 = 16 e 5 2 = 25
Portanto, os números primos entre 16 e 25 são 17, 19 e 23.

Input : 10
Output: Primes in the range 100 and 121 are:
        101
        103
        107
        109
        113


// CPP 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;
}


Saída:
Os números primos no intervalo 2500 e 2601 são:
2503
2521
2531
2539
2543
2549
2551
2557
2579
2591
2593



Consulte o artigo completo sobre a conjectura de Legendre para obter mais detalhes!


Quer aprender com os melhores vídeos com curadoria e problemas práticos, confira o C Foundation Course  for Basic to Advanced C.