Problem H
Legendre's Conjecture
A conjecture is a proposition or conclusion based upon incomplete information to which no proof has been found. In other words, it has neither been proved nor disproved.
Legendre’s Conjecture states that there is always at least one prime number between any two consecutive natural numbers’ squares. Write a program that prompts for an integer $n$. Then, using a while loop, or while loops, it lists the primes between $n^2$ and $(n+1)^2$. The conjecture has been verified for all $n$, where $1 \leq n \leq 2 \cdot 10^9$.
Hint: Use nested while loops.
Another hint: Reuse code you already wrote in the previous question.
Input
Input consists of one line containing one integer $n$, where $1 \leq n \leq 300$.
Output
Output all the prime numbers between $n$ and $n^2$ in ascending order, where each prime is on its own line.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 |
Primes in the range 100 and 121 are: 101 103 107 109 113 |
| Sample Input 2 | Sample Output 2 |
|---|---|
18 |
Primes in the range 324 and 361 are: 331 337 347 349 353 359 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 |
Primes in the range 4 and 9 are: 5 7 |
| Sample Input 4 | Sample Output 4 |
|---|---|
204 |
Primes in the range 41616 and 42025 are: 41617 41621 41627 41641 41647 41651 41659 41669 41681 41687 41719 41729 41737 41759 41761 41771 41777 41801 41809 41813 41843 41849 41851 41863 41879 41887 41893 41897 41903 41911 41927 41941 41947 41953 41957 41959 41969 41981 41983 41999 42013 42017 42019 42023 |
| Sample Input 5 | Sample Output 5 |
|---|---|
4 |
Primes in the range 16 and 25 are: 17 19 23 |
