Sum of prime numbers up to 2 million

Stop forcing this.
It's not funny.
It will not replace the fizzbuzz meme.
It will never become a meme.
Just fuck off.

>>8810299
>be me
>walk into job interview
>fucking kill yourself op
>whiteboard walks in
>end your life
>fuck you
>your application is to be reviewed
Is op gay?

File: prime2.jpg (85KB, 1021x620px) Image search: [Google]

85KB, 1021x620px

Made a progress report if anyone wants to know how close we are

The calculation would probably be faster if you didn't print out every prime number to the console

>>8810315
Yeah but I'd rather wait a bit longer and know my progress than be left in the dark.

https://pastebin.com/Rvqsj43q
m = 2*10**6
def fast__primes_under(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
n = n-n%6+6
correction = 2-(n%6>1)
sieve = [True] * (n/3)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = [False] * ((n/6-k*k/6-1)/k+1)
sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] * ((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

print sum(fast__primes_under(m))

4 hours later and progress is becoming a lot slower as expected

File: prime3.jpg (44KB, 651x486px) Image search: [Google]

44KB, 651x486px

Forgot this

>>8810591
>>8810314
>>8810299
1. use fermat's test
2. use pypy at least

File: 1324495756803.png (2KB, 203x219px) Image search: [Google]

2KB, 203x219px

>not using RSA to check for primes
Op, you are like a little baby

>>8810317
>Yeah but I'd rather wait a bit longer and know my progress than be left in the dark.

>Not just printing a prime every 100 primes or so

We are dealing with a Computer Science PhD here I see.

File: Screenshot from 2017-04-07 21-59-31.png (74KB, 864x761px) Image search: [Google]

74KB, 864x761px

>>8810428

>>8810990
http://www.wolframalpha.com/input/?i=sum+of+the+first+2+million+primes

top kek retardo here doesn't even know how to properly find primes.
Everyone point at the retard and laugh.

File: Hooky_patrick.jpg (76KB, 400x300px) Image search: [Google]

76KB, 400x300px

FUCKING PYTHON FAGS GET OUT REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE

>>8810299
silly CS majors.

I'll let you know when I have something useful for you to program.

t.engineer

>>8810428
>https://pastebin.com/Rvqsj43q
Jesus that is ugly.

>>8810990
>he didn't get the time it took

now you have to do it again

>>8810299
>I can even do it on Python
How long does it take?

genuinely interested matlab takes about 50 seconds.

>>8811078
65 ms on my machine.

>>8810299
using a D-wave I can hit 2^1500 you people hating on CS and Quantum computers should just all learn to behave

File: 2dd.jpg (15KB, 300x300px) Image search: [Google]

15KB, 300x300px

>>8811099
slow down there champ please

>>8810990

are you sure that isn't a unix timestamp

3050 seconds in C++ using a very shitty algorithm

I'm pretty interested in primes myself. My dream job in the future is as a cryptographer. I'll do some prime tests myself and post my results later.

>>8811001
>sum of the first 2 million primes
>all prime numbers below 2 million
Learn to read, kekold

>>8810990
made a sieve in Forth, got same answer in 0.2 seconds

>>8810589
>4 hours later
OP must either be a code monkey or trolling

>He didn't use dynamic programming
Shithead needs to fuck off from CompSci. The field is so tainted as it currently is.

File: baited.png (24KB, 404x250px) Image search: [Google]

24KB, 404x250px

Pretty sure this is bait because I just wrote the most naive sieve of eratosthenes ever (https://pastebin.com/cyt81FYa) and this is the result

File: primes.png (43KB, 625x981px) Image search: [Google]

43KB, 625x981px

Got the answer in 0.021057 s in Go. Anyone who does not know the sieve of Eratosthenes belongs neither in /g/ nor in /sci/.

>>8810299
>meme snake

print(142913828922)

File: Untitled.png (1KB, 145x86px) Image search: [Google]

1KB, 145x86px

>>8810299
>not scrolling into infinity

How do you guys actually get the result in less than 1 second?
My approach takes about 360 seconds or 6 minutes, which is better than OP but still slow. But for 2 million numbers i figured that's normal.

>>8812948
Why not have multiple instances open all running their own set range of numbers at the same time? Use all the cores of your CPU.

>>8812948
The basic trick is that you can severely reduce the number of multiplications/moduli necessary by storing all prior results. To check whether a number N is prime, you don't need to check whether it's divisible by any number smaller than N, it's sufficient to check on every prime smaller than sqrt(N). So first you check whether all numbers smaller than N are divisible 2. Then you check whether they are divisble by 3. You don't need to check whether they are divisible by 4 because it was already divisible by 2, so it's not a prime. You go on like that. That is basically the most naive kind of fast algorithm here, there are more sophisticated ones, but it already manages to get your sum in human time.

In python this would look like

def sum_primes(N):
nums = np.arange(2, N, 1, dtype=int)
prime = np.zeros_like(nums, dtype=bool)
for i in range(int(np.sqrt(len(nums)))):
if ~prime[i]:
prime[~prime & (nums > nums[i])] = nums[~prime & (nums > nums[i])] % nums[i] == 0
return np.sum(nums[~prime])

There are faster solutions in Python in this thread, but the code here is very simple and easy to understand.

>>8812955
The problem is not easily parallelized. Problem is that every thread needs to rely on previous calculations in order to be efficient. There's probably some way to get it working, but with all the threads constantly waiting on each other I doubt it's any speed-up at all.

>>8812967
>prime[~prime & (nums > nums[i])] = nums[~prime & (nums > nums[i])] % nums[i] == 0

>
There are faster solutions in Python in this thread, but the code here is very simple and easy to understand.
>easy to understand

fuck off with that pile of puke

>>8812980
are you for real? any additional thread will be waiting at the last prime tested, the further along the sum the larger the speedup....

>>8812967
>numpy
that's cheating.

this standard python (3) approach does it in 75 seconds on my machine

[code]

def test(N):
allNumbers=set([i for i in range(2, N+1)])

currentNumber = 2
usedNumbers = [2]
while currentNumber < int(N**0.5)+1:
cont = False
for used in usedNumbers:
if (used!=currentNumber and currentNumber%used==0):
currentNumber = currentNumber +1
cont = True
break
if cont==True:
continue
print(str(currentNumber)+" is used.")
usedNumbers.append(currentNumber)
multiples = set([i for i in range(2, N+1) if i%currentNumber==0])
multiples.remove(currentNumber)
allNumbers = allNumbers-multiples
currentNumber = currentNumber + 1

totalSum = 0
for prime in allNumbers:
totalSum += prime
return totalSum

[/code]

File: 1343606256089.jpg (29KB, 551x412px) Image search: [Google]

29KB, 551x412px

>>8813038
nigger what are you doing

>>8813038
If you think numpy is cheating then you don't know the first things about python. Also, if you are looking for code that is working with only pure python and even faster than my solution, then look for >>8810428. It looks ugly and is opaque as shit, but it's surprisingly fast (65 ms on my machine vs. 4 sec).

>>8813038

That's some elegant Python

File: 1491619371076.png (114KB, 256x256px) Image search: [Google]

114KB, 256x256px

>>8810990
it's okay anon
I like it

>>8813038
>allNumbers=set([i for i in range(2, N+1)])
correct me if I am wrong, but can't that potentially create a massive set which is not at all memory efficient?

>allNumbers = allNumbers-multiples
why no -= ?

>currentNumber = currentNumber + 1
why no +=?

>>8811099
bruh, that ain't what D-Wave machines do

>>8810299
>>8810314
>>8810591
why this piece of shit slow trash? even printing each number in c# wouldn't take so long

>>8810299
Are you a CS student?

>>8813066
I hate the same Python. I prefer Apollo. That's not a programming language though.

>>8810315
Not by much

>>8810841
>thinking printing output is what is making this code slow

Please don't comment in CS threads anymore

guys I need some help, I wrote this program that works for sum of primes smaller than 1000 but it does not want to print out a value if I want to go higher to 10000 for example.

sprim = 2

primed = range(sprim,primes)

prima = sprim

while prima < primes:
prime = [(prima*prim) for prim in range(sprim,primes)]
for prims in prime:
if primed.count(prims) is not (sprim-sprim):primed.remove(prims)
if primed.index(prima)+(sprim/sprim) >= len(primed):break
prima = primed[primed.index(prima)+(sprim/sprim)]

print sum(primed)

File: primemaker.png (9KB, 601x270px) Image search: [Google]

9KB, 601x270px

>>8813213
fuck I copied it wrong and it doesnt even show up right

primes = 1000

sprim = 2

primed = range(sprim,primes)

prima = sprim

while prima < primes:
prime = [(prima*prim) for prim in range(sprim,primes)]
for prims in prime:
if primed.count(prims) is not (sprim-sprim):primed.remove(prims)
if primed.index(prima)+(sprim/sprim) >= len(primed):break
prima = primed[primed.index(prima)+(sprim/sprim)]

print sum(primed)

Here's a collection of Haskell one-liners to produce the list of all primes,
and from which one can read of several algorithms

https://wiki.haskell.org/Prime_numbers_miscellaneous#One-liners

and here are generally a bunch of algorithms that do that

https://wiki.haskell.org/Prime_numbers

File: crappy.png (61KB, 479x443px) Image search: [Google]

61KB, 479x443px

Q6600
C is fucking fast.
I did a simple sieve and used the -O3 flag in gcc.

>>8810428
Doing this took 0.1 secs. .

File: IMG_20170408_203324093.jpg (1MB, 2592x1456px) Image search: [Google]

1MB, 2592x1456px

r8 my shit code

>>8813219
Newfag

>>8813285
why am I newfag

>>8812980
Actually it should be fairly easy to parallelize it since if a number can be prime factored the smaller factor cant be larger than the square root of the number being tested. So if you wanna test if 101 is a prime number you only need to go as high as to check if the primes below 10 is a factor of 101. So if you have found all primes below 20 you can find all primes up to 400 without finding additional ones.

File: 1452414848282.jpg (25KB, 403x403px) Image search: [Google]

25KB, 403x403px

>>8812980
>>8812992
lrn2thread for fuck sake

>>8813282
delet this

File: 11248293_1671913373082423_558510161_n.jpg (13KB, 320x320px) Image search: [Google]

13KB, 320x320px

>>8813282
>if i:

File: Screenshot_2017-04-09_04-01-00.png (22KB, 820x514px) Image search: [Google]

22KB, 820x514px

>>8810299
Now sum all the primes less than or equal to 10 billion in less than ten minutes.

>>8813532
Fun fact: If you use Wilson's theorem as a primality test, that probably takes years.

(think of the _ as whitespace)

totalSum = 0
for i in range(2, 10000000001):
__fac = math.factorial((i-1))
__if (fac+1) % i == 0:
____print(str(i)+" is prime.")
____totalSum+=i
print(totalSum)

My machine took 10 seconds to compute the first 5000 primes, then it took another 10 seconds for the next 2000. And later, for the primes between 15,000 and 20,000, it took over a minute.

https://en.wikipedia.org/wiki/Wilson's_theorem

Is OP just looking for very efficient ways to solve the prime number search?

>>8810317
it took less than 5 seconds for me with python

There isn't a formula to give the nth prime, right? I'm trying to make one and I made a base-10 digit index expression that returns the value of the nth digit in any number and a recursive formula from the long division process. I was hoping to rewrite the recursive solution as a gemeotric series and solve to give a test for rationality but I'm stuck. Advice/help?

https://projecteuler.net/problem=10
>Find the sum of all the primes below two million.

For some reason I misread this as "Find the sum of the first two million primes"
I got the code to work in python but my computer would take forever to calculate that.

>>8813558
The factorials are probably hurting you there. Can't you cache the previous factorial and multiply it by the new i-1 to go much faster?

>printing out the sum in a string
>not just computing it all then printing out a final answer

it's like you have never heard the word optimization before.

>>8813651
There aren't any good formulas for that, no. Anything you get is going to be ugly to write down and computationally hard. Keep trying though cause it's still fun to fuck around with trying to find formulas for primes.

File: 1457640927125.gif (774KB, 276x220px) Image search: [Google]

774KB, 276x220px

>>8813665
>2000000!
yes that will work

I got:

142913828920

Don't know if it's right desu.

>>8813655
>my computer would take forever to calculate that.
Why?

It literally took less than a second for my shitty JavaScript code to finish.

https://pastebin.com/qEWHfM3M

>>8814900
>>8814913
Forgot to add 2 at the beginning.

Should be 142913828922.

>>8810299
Look mom, I posted it again.

>>8810299
Great, now find the cure for cancer while designing a rocket launchable to mars otherwise you are still a brainlet.