This is all about on efficiency of the program, the faster the better, something which python is bad at, so other languages are also accepted (in English that is)
The most basic way of doing this is by checking whether all numbers between 1 and p (the number we are gonna check whether prime or not) are not factors of p
This can be easily sped up by only checking numbers from $1$ to $\lfloor\sqrt{p}\rfloor$ as factors,
Also prime numbers after $2$ and $3$ come as $6n\pm1\ , \forall n ∈ I$ this too can be exploited
Are there are any more techniques to make this faster?
Make your own program and report the time it took for finding all prime numbers from $1$ to $1000000$ ( if faster than everyone else put up your program as well )
For python, if you want to calculate the time it takes for it do so, you will have to import the time module and use the function time
1 2 3 4 5 6 

$\textbf{No using inbuilt modules if any which contain prime numbers or which contain}$ $\textbf{all the numbers to 1000000 and operating Eratosthenes sieve on it}$
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top Newest@Anonymous1 Assassin want to have a go at this(I see you have become recently active after quite a while), I’ll find out the complexity if you are able to make a program fast enough,if you want
Log in to reply
@Jason Gomez...I can't...JS isn't just cut out for this kinda number problem...I'm out.
Log in to reply
No probs, (this is anyway a dead discussion almost, the sieve can’t be defeated)
Log in to reply
lol yeah
Log in to reply
@Percy Jackson Here’s a way to exercise those chubby fingers, try beating David’s time using JavaScript(if you have learnt enough python, and can make a program faster than mine, then go on and do that too)
Log in to reply
bruh
My fingers are not chubby.
Log in to reply
But … Pipes told they were?.!
Log in to reply
Log in to reply
I don’t know anything about JavaScript, I assume it’s like Java with extras for better web page creations so forget the UI part and we have Java which should perfectly work
Log in to reply
I will try to make it, but JavaScript's better for web design, and that kind of stuff. It doesn't handle numbers too well, that's Python's job. JS is totally different from Java. Java has more of a C structure and syntax than JS.
Log in to reply
I checked the complexity of the programs and found out that the sieve is of $O(n)$ while mine is at $O(n^{1.2})$ and both of our programs are almost equally good at 2600, below mine is better, higher the sieve is way better
Log in to reply
@num IC Didn’t include yours in this analysis because it was a little slow (if you want it to be done also just ask )
Log in to reply
no problem.
it's nice that you posted this challenge.
i learned a lot (eg i was not aware that using set is fast).
Log in to reply
Log in to reply
Updates : My Python app can’t handle $10^8$ using David’s program( immediate crash ), and also as expected my program is actually in exponential time(or maybe it’s just that the app can’t use that much of RAM?) Either way both of the programs have failed outside the scope of what they were asked to do
Log in to reply
i assume your number above is 100 mio (100.000.000).
Log in to reply
Log in to reply
Red is the sieve and black is mine( I don’t know why but that thing looks like it wants to not go straight even in logarithm, looks like it might change to exponential time as I do higher numbers, but can’t wait that long)
Log in to reply
The sieve should take about 100 seconds for $10^8$ while mine will take 1000 seconds or higher
Log in to reply
This is the code I used
Log in to reply
I am confused did they make the environment faster? It’s taking only 2.490349292755127 seconds in it
Log in to reply
i assume the bril env runtime depends on the other processes that run on your PC and/or on the web trafic.
Log in to reply
Log in to reply
i tried this n* 6 +/ but it takes a similar time:
Log in to reply
At 100K mine runs at 0.144561767578125 seconds
Log in to reply
Um num, I think u missed a zero, it’s supposed to be one million not 100K
Log in to reply
yeah, i know. 1 mio in bril env creates a time out.
Log in to reply
Yeah, that's to be expected. For small ranges of numbers it makes a big difference, but the larger the range, the less effective it will be.
Log in to reply
As a reference, this is one implementation of the Sieve of Eratosthenes (generally the fastest method, but against the rules of the discussion). Time to beat: 800ms
Log in to reply
I know this makes my job harder, but in the multiples in prime part, I think python does a linear search, so if it is changed to a binary search it can be made faster
Log in to reply
Although
primes
is a set, so isn't it just using the hash function to search?Log in to reply
Log in to reply
direct lookup.
I don't think it's quite a linear search for a set. It's aLog in to reply
$O(1)$, never even thought it would exist (practically)
My first time I have seenLog in to reply
Log in to reply
Log in to reply
That's true.
Log in to reply
great. even in bril env it is fast (i compared the checks til 100 000):
md6 3.5528910160064697 9592
all 3.5862386226654053 9592
siv 0.061120033264160156 9592
Log in to reply
Does that last part mean we can't use the Sieve of Eratosthenes? Because generating a list of numbers from $1$ to $1000000$ and applying it takes only 800ms for me. :)
Log in to reply
Yes :), the sieve is not allowed because it’s the most powerful technique and getting better than that is almost impossible, no challenge at all then
Log in to reply
Rats. :)
Log in to reply
Log in to reply
Log in to reply
@num IC If you want you could try this out, doesn’t involve ndimensional spheres and cubes this time lol
Log in to reply
i did it in bril env. only up to 100.000 and it took already 5 sec:
Log in to reply
There is this thing about python, you got to be careful of the slow processes, like the for i in p:, requires accessing each element of list p which takes a hell lot of time, maybe because of the way python only stores the address of each of its elements
Log in to reply
@Anonymous1 Assassin Try this out
Log in to reply
My best is at 3.303286075592041 seconds using python
Log in to reply