[ASSIGNMENT] Prime numbers contest: produce the longest possible list of prime numbers.

Question

Write an efficient program generating and displaying the largest possible list of prime numbers (starting with 2,3,5...) on SoloLearn. The largest will win ! Start your message with this number to make it easier to find the winner.

Answer 1

Isn't the largest number limited by the size of the variable?

Answer 2

2 to 149993

But it would take time to print the output.

https://code.sololearn.com/WCHMF2Hfhj74/?ref=app

Answer 3

757288 (check up to 115*10^5)
https://code.sololearn.com/c71ASb440eWP/?ref=app

Some notes for @VcC:
- firstly I took my previous realization of Sieve of Eratosthenes (you have seen it already in my assignment), but it reached Memory Limit at already 10*10^5 (value until which the code checks Primes).
- then I improved it about twice reaching Memory Limit at 19*10^5.
- on the next step I was able to improve it till Time Limit at 56*10^5.
I had no ideas how I can do it better, so I have looked in your solution (which I didn't checked before), which goes up to 81*10^5, and I have found that you don't return a list of Primes, but only calculates their amount in a range.
So I've made the same thing with my code and now it reaches Memory Limit at about 115*10^5 generating 757288 Primes!

P.S. I don't know what it depends on, but right now I was able to get 558597 (limit of check is 84*10^5) with your code before reaching Time Limit. So maybe it varies a bit depending on the Server load or something else.

P.P.S. According to the conversation in the topic, I rewrote my code on C++. But for a moment I have a Memory Limit at the same maximum value. So I will try to improve it somehow, checking the solution of @~swim~ (which I also had no time to look yet). So the work is going on...

Answer 4

@~ swim ~ and @VcC
My new record is: 2718160 Primes in range from 2 to 450*10^5 until Time Limit is reached!
Recently I have known about one interesting build-in type in Python. And its utilization allowed me to reach about 4 times higher memory limit here on SoloLearn. Now it is almost the best I can do here. With limit of 4.5*10^7 it reaches Time Limit and I do not see a way to improve it. But even if I find a way then with limit of 5*10^7 it reaches again Memory Limit (however, I still can gain more here using bit arrays). New code is here (in fact only couples of lines are different):
https://code.sololearn.com/cyfXpo7NBLCk/?ref=app

P.S. However, it is still not as good as Swim's code, which finds 5216954 Primes from 2 to 900*10^5 for about 1.9 seconds here on SoloLearn.

Answer 5

Nice bytearray. In fact you only need bits but much better than int ! Python interpreter is slow so sieves will always be slower unless you find a smart way to use prebuilt functions

You can reach 22 000 000 using smart data type (numpy ones) and prebuilt functions (l[0:n:k]) to avoid a slow python loop
https://code.sololearn.com/ccs14kkUrBMQ/?ref=app

Answer 6

No why ? Sololearn platforms limitation will be the most limiting factor

Answer 7

I was wrong. Need to search the error ^^

https://code.sololearn.com/cX802TS9J17s/?ref=app
2^31 -1 is the highest.
2^61 -1 is also a prime, but it overflows inside the calculations to test it. (the s*s part is killing it)

Answer 8

(2^607) -1
https://code.sololearn.com/c6988L2iwP0I/?ref=app

Answer 9

Great ! Big numbers indeed but the chzllenge here is the number of primes (ie 2 count as much a huge Mersenne primes).

Answer 10

yes. it only displays the total nr of prime and the biggest because the full list generates a time out.

Answer 11

well done
cpp can be 20 to 100 time faster than python

Answer 12

~ swim ~ Yes sure there are not all primes but primes can only be like this
put this in a sieve and it is 6 times more efficient than a naive sieve trying all integers

Answer 13

~ swim ~ it works. for ex my current code does this with 2j+1. Still o(n.loglogn) but with 1/2 factor which always good to take.

Answer 14

546024
https://code.sololearn.com/c58LnOJlqfXd/?ref=app

Answer 15

yes it is. based on sololearn time and memory limits. Memory limites could be turned around with more efficient data structure.

Answer 16

i will let others win this challenge gladfully. Even on mobile python on my samsung note8 i can do better :-)

Answer 17

good one ! past a limit primes can only be 6k-1 and 6k+1. also bit arrays structure uses 8 times less memory.