Need help with larger inputs

Here is the problem quote:
“Generate numbers from 1 to N such that each number has only 3 factors and the sum of these consecutive numbers is prime”
for eg:-
N=4, numbers are 1 , 4 , 9 (output)
and 1+4=5 (prime), 4+9=13 (prime)

I tried to solve the problem but takes more time with larger number (10^9), So anyone one can provide me with a more powerful logic to solve this for larger N.

Only perfect square will satisfy the condition. So now you can solve it in O(sqrt(n)*logn)

1 Like

So, is it an exploitation of the fact that two square numbers add up-to prime ???

Can you share question link?

Thank you very much for help and I really learned something from this.

This question was a part of a competition organised by my institute a week before and they have removed the link too so that’s way I can’t share the link with anyone :frowning: