[Question]
  [
[Legendre's Conjecture](https://en.wikipedia.org/wiki/Legendre%27s_conjecture) is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$.
# The Challenge
Make a program which only halts if Legendre's conjecture is false. Equivalently, the program will halt if there exists \$n\$ which disproves the conjecture.
# Rules
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the shortest program in bytes wins.
* No input shall be taken by the program.
* The program only needs to halt or not halt in theory; memory and time constraints shall be ignored.
* One may use methods other than checking every \$n\$ if they can prove their program will still only halt if Legendre's conjecture is false.
  
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~49~~ 47 bytes
A full program that stops only if there's some \$n\ge2\$ such that all \$x\in[(n-1)^2..n^2]\$ are composite.
```
for(x=n=2n;x-n*n;d?0:x=n*n++)for(d=x++;x%d--;);
```
[Try it online!](https://tio.run/##y0osSyxOLsosKNHNy09J/f8/Lb9Io8I2z9Yoz7pCN08rzzrF3sAKKKCVp62tCZJMsa3Q1rauUE3R1bXWtP7/HwA "JavaScript (Node.js) – Try It Online")
### Commented
```
for(                  // outer loop:
  x = n = 2n;         //   start with x = n = 2
  x - n * n;          //   stop if x = n²
  d ? 0 : x = n * n++ //   if d = 0, set x = n² and increment n
)                     //
  for(                //   inner loop:
    d = x++;          //     start with d = x and increment x
    x % d--;          //     stop if d divides x; decrement d
  );                  //     if we end up with d = 0, then x is prime
```
[Answer]
# [Raku](https://github.com/nxadm/rakudo-pkg), 34 bytes
```
1...{is-prime none $_²..($_+1)²}
```
[Try it online!](https://tio.run/##K0gtyjH7/99QT0@vOrNYt6AoMzdVIS8/L1VBJf7QJj09DZV4bUPNQ5tq//8HAA "Perl 6 – Try It Online")
Counts upwards until it finds a number where none of the given range are prime.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~17~~ 11 bytes
```
∞.∆DnÅNs>n@
```
[Try it online!](https://tio.run/##ASYA2f9vc2FiaWX//@KIni7iiIZEbnM@bkTDhVDOuC7DgcW4w6XiiaD//w "05AB1E – Try It Online")
*-6 bytes thanks to @ovs*
## Explained
```
∞.∆DnÅNs>n@ 
∞                   Push an infinite list
 .∆                 Find the first item in that list that:
   D                  
       s>n              (n+1)^2 is
          @             larger or equal than
    nÅN                 the next prime from n^2
```
[Answer]
# [R](https://www.r-project.org/), ~~60~~ ~~55~~ 54 bytes
*Edit: -1 byte thanks to Robin Ryder*
```
while(sd(sapply(lapply(T^2:(T=T+1)^2,`%%`,2:T),all)))T
```
[Try it online!](https://tio.run/##K/r/vzwjMydVozhFozixoCCnUiMHQoXEGVlphNiGaBtqxhnpJKiqJugYWYVo6iTm5Ghqaob8/w8A "R – Try It Online"), or, since it's rather boring to run a program that (probably) never halts and produces no output, [try](https://tio.run/##K/r/vzwjMydVQyPPtrg0V6M4saAgp1IjB0KFxBlZaYTYhmgbasYZ6SSoqiboGFmFaOok5uRoAkF1QVFmXolGskaITp6mZu3//wA "R – Try It Online") a slightly longer version (exchanging `n=sum(` for `any(`) that prints n and the number of primes in the interval (n-1)^2..n^2 for each n>2.
Commented original version:
```
while(                                  # keep looping as long as...
    any(                                # there is at least one true result among...
        sapply(T^2:(T=T+1)^2,           # the loop from T^2 up to (T+1)^2
                                        # (& use this opportunity to increment T)...
            function(x)all(x%%(2:T))    # tested for primality by checking that all 
                                        # modulo divisions from 2..T have a non-zero result
        )
    )   
){}
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
‘ɼ²ÆCµƬ
```
A niladic Link which, if the conjecture is False, will yield a list of counts of primes between \$2\$ and \$k^2\$ where \$k\$ is the zero-based index of the element (although the zero-indexed element will be `None` rather than `0`). The final value in the list will be the count of primes between \$2\$ and \$n^2\$ (the next term would be the count between \$2\$ and \$(n+1)^2\$, and would be equal to that).
Note: Since this uses one of Jelly's prime related built-ins, this is subject to the underlying implementation's ([sympy](https://docs.sympy.org/latest/index.html)'s) primality check, and `help(sympy.ntheory.isprime)` states *...[If] the number is larger than 2^64, a strong BPSW test is performed. While this is a probable prime test and we believe counterexamples exist, there are no known counterexamples)*.
**[Try it online!](https://tio.run/##ARcA6P9qZWxsef//4oCYybzCssOGQ8K1xqz//w "Jelly – Try It Online")**
### How?
Collects the counts of primes between \$2\$ and \$(k+1)^2\$ starting with \$k=0\$ until repetition would be present by appending the result. This implies there are no new primes between \$(k+1)^2\$ and \$(k+2)^2\$ (i.e. \$n^2\$ and \$(n+1)^2\$). The final result, if any, will have a leading `None` - the initial input to the function that performs the counting.
```
‘ɼ²ÆCµƬ - Link: no arguments
      Ƭ - collect up (the initial input (None) and each result) until repetition:
     µ  -   apply the monadic chain - i.e. f(x=previousResult):
 ɼ      -     recall (k) from the register (initially 0), apply, store back, and yield:
‘       -     increment -> k+1
  ²     -     square -> (k+1)²
   ÆC   -     count primes from 2 to (k+1)² inclusive
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
²+æR$Ṇµ2#
```
[Try it online!](https://tio.run/##y0rNyan8///QJu3Dy4JUHu5sO7TVSPn/fwA "Jelly – Try It Online")
-1 byte thanks to caird coinheringaahing  
-1 byte thanks to Jonathan Allan
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), ~~67~~ 62 bytes
```
_¶¶_
{`(_+)¶_*(¶_+)
_$1$2$2$1$1_
¶(_+)¶(?!_*(?!(__+)\2+$)\1)
```
[Don't try it online!](https://tio.run/##K0otycxL/P@fK/7QtkPb4rmqEzTitTWBLC0NIKGtyRWvYqhiBISGKobxXIe2QWQ17BWBCuwVNeKB3BgjbRXNGENNrv//AQ "Retina 0.8.2 – Try It Online") Instead, [try](https://tio.run/##K0otycxLNPz/3zsh/tC2Q9viuZRUtJWqEzTitTWBPC0NIKGtyRWvYqhiBISGKobxXIe2QWQ17BWBCuwVNeKB3BgjbRXNGENNrv//DQ0A "Retina – Try It Online") a [Retina 1](https://github.com/m-ender/retina/wiki/The-Language) version which takes as input the number of iterations. Explanation:
```
_¶¶_
```
The working area contains `n+1`, `n²` and `(n+1)²`, where `n` starts at `0` but is immediately incremented (saving 5 bytes over my previous answer which started with `n=1`).
```
{`
```
Repeat until Legendre's conjecture is false.
```
(_+)¶_*(¶_+)
_$1$2$2$1$1_
```
Increment `n`; the old `(n+1)²` becomes the new `n²` and the new `(n+1)²` is calculated.
```
¶(_+)¶(?!_*(?!(__+)\2+$)\1)
```
If none of the numbers between `n²` and `(n+1)²` are prime, then delete `n²` and `(n+1)²`, which causes the loop to terminate, as neither stage can now match.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~194~~ ~~180~~ 169 bytes
```
#include<gmp.h>
main(){mpz_t n,l,h;for(mpz_init_set_ui(n,1),mpz_init(l),mpz_init(h);mpz_mul(l,n,n),mpz_add_ui(n,n,1),mpz_mul(h,n,n),mpz_nextprime(l,l),mpz_cmp(l,h)<1;);}
```
[Try it online!](https://tio.run/##TY7NCsMgEITvfYpCLwqmkLOhryKyGhXWrSQKJaWvXqukf7eZ2fmGhcEB1HoKBFiMnVxMZ385RB2I8XtMm8pHEii8nK8L6z5QyGq1WZXASIxcfEKGf9pz2XUsyFCQoP2kjdmxL9gL/lcge8tpCdE26j0HMTXj@TRKLh@1PmFG7dY6YPv1BQ "C (gcc) – Try It Online")
-14 bytes thanks to ceilingcat!
-11 bytes again thanks to ceilingcat!
To test, here's one that outputs the prime in each range:
# [C (gcc)](https://gcc.gnu.org/), 352 bytes
```
 #include<stdio.h>
#include<gmp.h>
#define m(X) mpz_##X
main(){m(t) n,l,h;m(init_set_ui)(n,1);m(init)(l);m(init)(h);for(;;){m(mul)(l,n,n);m(add_ui)(n,n,1);m(mul)(h,n,n);
 printf("In (");
 m(out_str)(stdout,10,l);
 printf(", ");
 m(out_str)(stdout,10,h);
 printf("): ");
m(nextprime)(l,l);if(m(cmp)(l,h)>0)return;
 m(out_str)(stdout,10,l);
 puts("");
}}
```
[Try it online!](https://tio.run/##fZBBasQwDEX3OYVJNhJ4ysy2KbPvDWYXgmPHBksJjg2lZa5e105DO5t2J/3/viSkTrNSOYvOsfJp0i9bnNzyZK/NjzLTuveTNo61ILihoPV96LpbQ6NjwA@CiIKll7YncOzisOk4JIfA8oKHhuB/S4u9WQL0fQ1T8sWULLkC4zQd0SO82/bbbsQaHEcD7SsLaKtAsKSyMAaEcnyp5eUs/SMqxd@gfQTxeScJWL/FIpKud5VZzgCBorW2Fq9nDDqmwP9vT3GDts6733P@VMaP85ZPvvzzCw "C (gcc) – Try It Online")
Note: This is probably very optimizable. When certain users inevitably improve the solution, I'll update. ;)
[Answer]
# [Python 2](https://docs.python.org/2/), 45 bytes
```
i=k=P=1
while~i*~i-k:P*=k;k+=1;i+=i*i<k>0<P%k
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P9M22zbA1pCrPCMzJ7UuU6suUzfbKkDLNts6W9vW0DpT2zZTK9Mm287AJkA1@/9/AA "Python 2 – Try It Online")
[Here's a demonstration](https://tio.run/##BcFLCoAwDAXAvafIRmirgj8EP/EMvYIL0UckihTEjVevM9cb9lPrGMHCnqvk2XGsH9yHQgbvWEbJuBqRMRwmmcvJ@FTIkRHSMxCU7kW31TRd3vbW2njd0ECSI/4 "Python 2 – Try It Online") of the code halting if we modify it to claim that all of `range(36,49)` is non-prime.
We use the [Wilson's Theorem](https://codegolf.stackexchange.com/a/27022/20260) prime generator. We count up potential primes `k`, and the condition `P%k>0` is met exactly for primes. Except, we use `P*=k` instead of `P*=k*k` which makes `k=4` also be called prime, but that doesn't matter here.
Here's how we halt if there's not prime between two consecutive squares. The value `i` tries to track the smallest number so that the square `i*i` is at least the current potential prime `k`. Every time we hit a prime `k`, we update `i` by checking if `i*i<k`, and if so, increment `i`. This makes it so that `k<=i*i` afterwards. But, if there is no prime between `i**2` and `(i+1)**2`, then `i` won't update in that interval, and `k` will reach all the way to `(i+1)**2`. The `while` loop conditions checks for this (writing `~i*~i` for `(i+1)**2`) and terminates the loop if it happens.
---
**73 bytes**
```
n=2
while any(all(k%i for i in range(2,k))for k in range(n*n,~n*~n)):n+=1
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P8/WiKs8IzMnVSExr1IjMSdHI1s1UyEtv0ghUyEzT6EoMS89VcNIJ1tTEySWjRDL08rTqcvTqsvT1LTK07Y1/P8fAA "Python 2 – Try It Online")
A more direct approach of checking that each interval between squares contains a prime, based [on the solution of Manish Kundu](https://codegolf.stackexchange.com/a/208909/20260)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 11 bytes
First attempt:
```
[N>nÅMNn‹#]
```
Fixed (after @ovs notes):
```
[NÌnÅMN>n‹#
```
## Explanation:
```
[NÌnÅMN>n‹# 
[                     Infinite Loop
 N                    Current loop index (starts from 0 to Infinity)
  Ì                   add 2 ( we want to start from N=1 instead of N=0)
   n                  Squaring - (N+1)**2
    ÅM                Find the previous prime. Highest prime less than (N+1)**2
      N>               Push Current loop index + 1
        n              Squaring - N**2
         ‹             Does  Highest prime less than (N+1)**2 < N**2  ?
          #            If true, break the loop
```
[Try it online!](https://tio.run/##yy9OTMpM/f8/2u9wT97hVl8/u7xHDTuV//8HAA)
[Answer]
# [Io](http://iolanguage.org/), 124 bytes
```
method(x :=1;loop(s :=0;for(i,x*x,x*(x+2)+1,if(Range 1 to(i)asList select(o,i%o<1)size<3,s :=1;break));if(s<1,break);x=x+1))
```
[Try it online!](https://tio.run/##JYwxDkIhEAWvQmOyKxSinfBvYGVtgwq6EdkfloJ4eSRaTPKmeEM8kjou6jLesT35Dn2adZl5BZlz5xJXINO3fQJd71FbQwnOoTyisqoxEAY5kTQlMcdbAza0YW9R6BP9wciveK0xvBDdvIq35q@uL11bxJEA1VqptFzGFw "Io – Try It Online")
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~11~~ 10 bytes
```
`@U_Yq@QU<
```
[Try it online!](https://tio.run/##y00syfn/P8EhND6y0CEw1Ob/fwA "MATL – Try It Online")
-1 byte thanks to Luis Mendo. Otherwise, pretty straightforward.
```
`  % Start a loop
@  % Push loop index (n)
U  % square
_Yq % Get next prime
@QU % Loop index plus one, squared
<   % Continue loop if the prime is smaller than this.
```
[Answer]
# [><>](http://esolangs.org/wiki/Fish), 51 bytes
```
/;?)*:&+1}::&<
\~:*>2:}}:}=?^:}}:}$%?2~1+l3+1.15a&4
```
[Try it online!](https://tio.run/##S8sszvj/X9/aXlPLSk3bsNbKSs2GK6bOSsvOyKq21qrW1j4OTKuo2hvVGWrnGGsb6hmaJqqZ/P8PAA)
[Try it online! (2)](https://tio.run/##S8sszvj/X9/aXlPLSk3bsNbKSs2GK6bOSsvOyKq21qrW1j4OTKuo2hvVGWrnGGsb6hmapqqZ/P8PAA) shows the program terminating if starting above last prime in first range.
**Explanation**
```
/;?)*:&+1}::&<
\~:*
```
Prime branch, checks if first found prime is below \$(n+1)^2\$ and then increments \$n\$ and jumps up to the next range, otherwise terminates
```
    >2:}}:}=?^
```
Ends trial division if we have found a prime
```
              :}}:}$%?2~1+l3+1.
```
Branch-free trial division
```
/
\                             .15a&4
```
Initial values, starts at 10 trying to find primes below \$4^2\$
[Answer]
# [Python 3](https://docs.python.org/3/), ~~107~~ ~~99~~ ~~88~~ ~~86~~ ~~90~~ ~~86~~ 79 bytes
```
n=2
while n:n+=0<sum(min(i%j for j in range(2,i))for i in range(n*n,~n*~n))or-n
```
[Try it online!](https://tio.run/##K6gsycjPM/7/P8/WiKs8IzMnVSHPKk/b1sCmuDRXIzczTyNTNUshLb9IIUshM0@hKDEvPVXDSCdTUxMklokQy9PK06nL06rL09TML9LN@/8fAA "Python 3 – Try It Online")
Initially, n=2. Then it checks if any of the 2n numbers between n^2 and (n+1)^2 are prime or not. If yes, then n is incremented, otherwise n is set to 0 and the loop terminates.
*-7 bytes thanks to Jo King*
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 30 bytes
```
For[n=1,NextPrime[n++^2]<n^2,]
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78/98tvyg6z9ZQxy@1oiSgKDM3NTpPWzvOKNYmL85IJ/b///8A "Wolfram Language (Mathematica) – Try It Online")
Special thankks to @att for saving 9 bytes
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~88~~ 84 bytes
Saved 4 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!!!
```
q;h;i;j;f(n){for(h=n=1;h;++n)for(h=0,i=n*n;q=j=++i<~n*~n;h|=q)for(;++j<i;)q=q&&i%j;}
```
[Try it online!](https://tio.run/##JYrNCoMwEAbveQovStZYaM@f@zASiNlAt2zpzZ9Xj6HObYaJjzXGWg0ZgoLklbb0@frMyq8WQ1C6/TkJ66gwLhyCzKeOpyLvbP@hnWUWkLENg/QFRxX9de9F1JPbXNdInuCOegE "C (gcc) – Try It Online")
Will run forever on an infinite machine (with new infinity-bit `int` types!) so long as there's always a prime number in the interval \$(n^2,(n+1)^2)\$.
Here's the same code modified to print the primes as they are found:
# [C (gcc)](https://gcc.gnu.org/), 161 bytes
```
q;h;i;j;f(n){for(h=n=1;h;++n)for(h=0,i=n*n;q=j=++i<~n*~n;h|=q){for(;++j<i;)q=q&&i%j;if(q)printf("Found prime %d in the interval (%d, %d)\n",j,n*n,(n+1)*(n+1));}}
```
[Try it online!](https://tio.run/##JU0xDoMwENt5RYQEuiOpVOYja1/RBQEpF5WjQbQLha@nUfFgy5Ytd5dH18UYaCQmTw4ENzcvMFqxdQq1Fjz91bCVSihYb7Xm5pDqEBq/NpyLVPUNEwYbypILT@wg4GthWR3kt/ktvUpuGlTRKxa1jkOSdVg@7VNB0ZuU411y4026MSC6xurPSPseU1VNLQtgtmUqwQFStscf "C (gcc) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), ~~12~~ 11 bytes [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
_²ôZÑ dj}f1
```
[Test it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=X7L0WtEgZGp9ZjE) (May cause your browser to explode!)
```
_               :Function taking an integer Z as argument
 ²              :  Z squared
   ZÑ           :  Z times 2
  ô             :  Range [Z²,Z²+Z*2]
      d         :  Any
       j        :    Prime
        }       :End function
         f1     :Return the first Z≥1 that returns false
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 12 bytes
```
+₁;?≜^₂ᵐ⟧₂ṗⁿ
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r/X/tRU6O1/aPOOXGPmpoebp3waP5yEGPn9EeN@///BwA "Brachylog – Try It Online")
### How it works
Brachylog will try to find a value `N` that fulfills the following program:
```
+₁;?≜^₂ᵐ⟧₂ṗⁿ
+₁            N+1
  ;?          [N+1, N]
    ≜         Try possible numbers, e.g. [5, 4]
     ^₂ᵐ      Map square [25, 16]
        ⟧₂    Range from min to max
          ṗⁿ  Succeeds if there is no prime in this range
```
[Answer]
# Scala, ~~98~~ ~~93~~ ~~91~~ 87 bytes
*-7 bytes thanks to Dominic Van Essen*
```
Stream.iterate(2:BigInt)(_+1)find(n=>n*n to n*n+2*n forall(x=>n to(2,-1)exists(x%_<1)))
```
Without `BigInt`, it could be made a few bytes shorter, but then it would overflow.
It first creates an infinite list starting at 2, then tries to find an `n` in that list such that every number `x` in the range `n^2` to `(n+1)^2` is composite.
[Try it in Scastie](https://scastie.scala-lang.org/x3HjWbAxRYeVxcYX28gqzA)
]