# Find all prime numbers from 1 to 1000000 using a program

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 import time timeBefore=time.time() print("hello") timeAfter=time.time() timeItTook=timeAfter-timeBefore#gives in seconds, will give zero in this example mostly because #printing one statement takes no measurable time 

$\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}$

Note by Jason Gomez
5 months, 1 week ago

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:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

My best is at 3.303286075592041 seconds using python

- 5 months, 1 week ago

@Anonymous1 Assassin Try this out

- 5 months, 1 week ago

@num IC If you want you could try this out, doesn’t involve n-dimensional spheres and cubes this time lol

- 5 months, 1 week ago

i did it in bril env. only up to 100.000 and it took already 5 sec:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import time strt = time.time() p=[] for n in range(2, 100001): is_p = True for i in p: if n%i == 0: is_p = False break if is_p: p.append(n) stop = time.time() print(stop-strt) print(p) __________________ Output: 5.19477391242981 

- 5 months, 1 week ago

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

- 5 months, 1 week ago

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. :)

- 5 months, 1 week ago

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

- 5 months, 1 week ago

Rats. :)

- 5 months, 1 week ago

You can put down your Eratosthenes sieve here, with a brief mention that it broke the rules(of this discussion), my aim is to beat it, one step at a time atleast

- 5 months, 1 week ago

Sure.

- 5 months, 1 week ago

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def get_primes(min_num, max_num): primes = set([p for p in range(min_num, max_num + 1)]) not_primes = set() prime = 2 while prime ** 2 <= max_num: multiples = prime ** 2 while multiples <= max_num: not_primes.add(multiples) if multiples in primes: primes.remove(multiples) multiples += prime keep_increasing = True while keep_increasing: if prime + 1 in not_primes: prime += 1 else: prime += 1 break return sorted(primes) 

- 5 months, 1 week ago

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

- 5 months, 1 week ago

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

- 5 months, 1 week ago

That's true.

- 5 months, 1 week ago

Although primes is a set, so isn't it just using the hash function to search?

- 5 months, 1 week ago

I haven’t used sets much so I didn’t know how it index’s and it looks like it index’s in favour of me, lol, yeah you can’t use the binary search so stuck with linear now( lemme try converting that set to a list in such a way it doesn’t compromise speed, mostly will fail, if it works I’ll tell)

- 5 months, 1 week ago

I don't think it's quite a linear search for a set. It's a direct lookup.

- 5 months, 1 week ago

Oh then it’s better than a binary search even lol

- 5 months, 1 week ago

My first time I have seen $O(1)$, never even thought it would exist (practically)

- 5 months, 1 week ago

I know. I sometimes wonder how much code I could have written better knowing about it... :)

- 5 months, 1 week ago

i tried this n* 6 +/- but it takes a similar time:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import time strt = time.time() p1=[2,3] til = 100001 n = 5 while n < til: is_p = True for i in p1: if n%i == 0: is_p = False break if is_p: p1.append(n) n+=2 is_p = True for i in p1: if n%i == 0: is_p = False break if is_p: p1.append(n) n+=4 stop = time.time() print('md6', stop-strt, len(p1)) strt = time.time() p2=[] n = 2 while n < til: is_p = True for i in p2: if n%i == 0: is_p = False break if is_p: p2.append(n) n+=1 stop = time.time() print('all', stop-strt, len(p2)) __________________________________ Output: md6 3.8270275592803955 9592 all 3.910518169403076 9592 

- 5 months, 1 week ago

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.

- 5 months, 1 week ago

Um num, I think u missed a zero, it’s supposed to be one million not 100K

- 5 months, 1 week ago

yeah, i know. 1 mio in bril env creates a time out.

- 5 months, 1 week ago

At 100K mine runs at 0.144561767578125 seconds

- 5 months, 1 week ago

This is the code I used

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from time import time from math import floor t1=time() prime=[2,3] for i in range(1,166667): p1=6*i-1 p2=6*i+1 check=True for factor in range(5,floor(p1**0.5+1),6): if p1%factor==0: check=False break if check: for factor in range(7,floor(p1**0.5+1),6): if p1%factor==0: check=False break if check: prime.append(p1) check=True for factor in range(5,floor(p2**0.5+1),6): if p2%factor==0: check=False break if check: for factor in range(7,floor(p2**0.5+1),6): if p2%factor==0: check=False break if check: prime.append(p2) print(time()-t1,len(prime)) 

- 5 months, 1 week ago

I am confused did they make the environment faster? It’s taking only 2.490349292755127 seconds in it

- 5 months, 1 week ago

i assume the bril env runtime depends on the other processes that run on your PC and/or on the web trafic.

- 5 months, 1 week ago

Can you try my code on your PC then?

- 5 months, 1 week ago

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

- 5 months, 1 week ago

The sieve should take about 100 seconds for $10^8$ while mine will take 1000 seconds or higher

- 5 months, 1 week ago

- 5 months, 1 week ago

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)

- 5 months, 1 week ago

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

- 5 months, 1 week ago

it's difficult to count the number of zeroes, so i propose to use other wordings for the big numbers to avoid misunderstandings.
i assume your number above is 100 mio (100.000.000).

- 5 months, 1 week ago

Yeah that’s right I think I’ll change to scientific notation then, more easier to count zeroes :)

- 5 months, 1 week ago

@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 )

- 5 months, 1 week ago

no problem.
it's nice that you posted this challenge.
i learned a lot (eg i was not aware that using set is fast).

- 5 months, 1 week ago

@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)

- 5 months, 1 week ago

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

- 5 months, 1 week ago

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.

- 5 months, 1 week ago

bruh

My fingers are not chubby.

- 5 months, 1 week ago

But … Pipes told they were?.!

- 5 months, 1 week ago

Nope...

- 5 months, 1 week ago

@Jason Gomez...I can't...JS isn't just cut out for this kinda number problem...I'm out.

No probs, (this is anyway a dead discussion almost, the sieve can’t be defeated)

- 5 months ago

lol yeah

@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

- 5 months ago