Sum of prime numbers up to 2 million

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

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

...

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.

FUCKING PYTHON FAGS GET OUT REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE

silly CS majors.

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

t.engineer

>pastebin.com/Rvqsj43q
Jesus that is ugly.

>he didn't get the time it took

now you have to do it again

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

genuinely interested matlab takes about 50 seconds.

65 ms on my machine.

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

slow down there champ please

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.

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

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

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

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

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

>meme snake

print(142913828922)

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

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.

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.

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.

>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

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

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

nigger what are you doing

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 . It looks ugly and is opaque as shit, but it's surprisingly fast (65 ms on my machine vs. 4 sec).

That's some elegant Python

it's okay user
I like it

>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 +=?

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

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

Are you a CS student?

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

Not by much

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

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

wiki.haskell.org/Prime_numbers_miscellaneous#One-liners

and here are generally a bunch of algorithms that do that

wiki.haskell.org/Prime_numbers

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

Doing this took 0.1 secs. .

r8 my shit code

Newfag

why am I newfag

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.

lrn2thread for fuck sake

delet this

>if i:

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

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.

en.wikipedia.org/wiki/Wilson's_theorem

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

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?

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.

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.

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.

>2000000!
yes that will work

I got:

142913828920

Don't know if it's right desu.

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

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

pastebin.com/qEWHfM3M

Forgot to add 2 at the beginning.

Should be 142913828922.

Look mom, I posted it again.

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