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 11 to p\lfloor\sqrt{p}\rfloor as factors,

Also prime numbers after 22 and 33 come as 6n±1 ,nI6n\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 11 to 10000001000000 ( 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 

No using inbuilt modules if any which contain prime numbers or which contain\textbf{No using inbuilt modules if any which contain prime numbers or which contain} all the numbers to 1000000 and operating Eratosthenes sieve on it\textbf{all the numbers to 1000000 and operating Eratosthenes sieve on it}

Note by Jason Gomez
1 week ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

My best is at 3.303286075592041 seconds using python

Jason Gomez - 1 week ago

Log in to reply

@Anonymous1 Assassin Try this out

Jason Gomez - 1 week ago

Log in to reply

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

Jason Gomez - 1 week ago

Log in to reply

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

num IC - 1 week ago

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

Jason Gomez - 6 days, 20 hours ago

Log in to reply

Does that last part mean we can't use the Sieve of Eratosthenes? Because generating a list of numbers from 11 to 10000001000000 and applying it takes only 800ms for me. :)

David Stiff - 1 week ago

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

Jason Gomez - 1 week ago

Log in to reply

Rats. :)

David Stiff - 1 week ago

Log in to reply

@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 - 1 week ago

Log in to reply

@Jason Gomez Sure.

David Stiff - 1 week ago

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

 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)

David Stiff - 1 week ago

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

num IC - 1 week ago

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

Jason Gomez - 6 days, 17 hours ago

Log in to reply

That's true.

David Stiff - 6 days, 10 hours ago

Log in to reply

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

David Stiff - 6 days, 10 hours ago

Log in to reply

@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 - 6 days, 9 hours ago

Log in to reply

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

David Stiff - 6 days, 9 hours ago

Log in to reply

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

Jason Gomez - 6 days, 9 hours ago

Log in to reply

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

Jason Gomez - 6 days, 9 hours ago

Log in to reply

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

David Stiff - 6 days, 9 hours ago

Log in to reply

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

num IC - 1 week ago

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.

David Stiff - 6 days, 22 hours ago

Log in to reply

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

Jason Gomez - 6 days, 20 hours ago

Log in to reply

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

num IC - 6 days, 19 hours ago

Log in to reply

At 100K mine runs at 0.144561767578125 seconds

Jason Gomez - 6 days, 20 hours ago

Log in to reply

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

Jason Gomez - 6 days, 18 hours ago

Log in to reply

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

Jason Gomez - 6 days, 18 hours ago

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.

num IC - 6 days, 18 hours ago

Log in to reply

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

Jason Gomez - 6 days, 18 hours ago

Log in to reply

I checked the complexity of the programs and found out that the sieve is of O(n)O(n) while mine is at O(n1.2)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

Jason Gomez - 6 days, 18 hours ago

Log in to reply

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

Jason Gomez - 6 days, 18 hours ago

Log in to reply

Jason Gomez - 6 days, 18 hours ago

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)

Jason Gomez - 6 days, 17 hours ago

Log in to reply

Updates : My Python app can’t handle 10810^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 - 6 days, 13 hours ago

Log in to reply

@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 - 6 days, 8 hours ago

Log in to reply

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

Jason Gomez - 5 days, 22 hours ago

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 )

Jason Gomez - 6 days, 13 hours ago

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

num IC - 6 days, 8 hours ago

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)

Jason Gomez - 6 days, 13 hours ago

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

Jason Gomez - 6 days, 9 hours ago

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.

Percy Jackson - 5 days, 14 hours ago

Log in to reply

bruh

My fingers are not chubby.

Percy Jackson - 5 days, 14 hours ago

Log in to reply

But … Pipes told they were?.!

Jason Gomez - 5 days, 14 hours ago

Log in to reply

@Jason Gomez Nope...

Percy Jackson - 5 days, 13 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...