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

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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

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

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)

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

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

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:

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

My best is at 3.303286075592041 seconds using python

Jason Gomez - 3 months, 3 weeks ago

@Anonymous1 Assassin Try this out

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

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

num IC - 3 months, 3 weeks 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

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

David Stiff - 3 months, 3 weeks 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

Rats. :)

@David Stiff – 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

@Jason Gomez – Sure.

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

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

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

That's true.

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

@David Stiff – 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)

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

@David Stiff – Oh then it’s better than a binary search even lol

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

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

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

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.

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

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

At 100K mine runs at 0.144561767578125 seconds

This is the code I used

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

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

@Num Ic – Can you try my code on your PC then?

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

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

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)

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

@Jason Gomez – 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).

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

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

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

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

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

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.

A Former Brilliant Member - 3 months, 3 weeks ago

bruh

My fingers are not chubby.

But … Pipes told they were?.!

@Jason Gomez – Nope...

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

A Former Brilliant Member - 3 months, 2 weeks ago

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

Jason Gomez - 3 months, 2 weeks 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

Math	Appears 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}$