Sum all primes below 2 million, 2 billion and 20 billion

Sum all primes below 2 million, 2 billion and 20 billion.
Last one is optional and kinda 'hardmode'

>mfw Sup Forums can't do it

Other urls found in this thread:

cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
en.wikipedia.org/wiki/Primality_test#Simple_methods
twitter.com/SFWRedditVideos

...

Literally just implement the sieve of Atkin in you language of choice

Damn. Only knew the sieve of eratosthenes. Learned something new today. Thanks!

import primesolver
print solveAllPrimes(2000000)


Stack overflow approved

I'm not making your homework

Wow that was easy.
Would this fly in a job interview?

#include

int main(void)
{
for (int p = 2; p

How is knowing how to do this going to be important for anything in any job? A really useful programmer or engineer would know that OEIS exists.

int sum = 0;
string line;
using (var reader = new StreamReader("allprimesbelow2mil.txt")){
while (line = reader.readLine()) {
sum += int.Parse(line);
}
}


Done.

It's a test to determine it you're not an idiot who brute forces like
If your answer is any kind of sieve, even an inefficient one, then you are good

primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x|x 0]

sum = foldr (+) $ primes [2..] 0

sumTillN n =
takeWhile (

Brute forcing may well be more appropriate if it's an implementation that is run infrequently and engineer time is more valuable than run time. If I have to implement an efficient sieve, I'm not going to do anything other that the most efficient sieve, so give me access to google and I'll happily implement whatever algorithm it presents me.

Oops I forgot a couple of lines in there.
#include

int main(void)
{
for (int p = 2; p

> give me access to google and I'll happily implement whatever algorithm it presents me.
literally Pajeet tier

Absolutely shit tier solution, kys

>literally Pajeet tier
Right.

You don't actually have a programming job, do you?

What's the problem with the solution? It's not like we're trying to get the world record list of primes.

I mostly work in pseudo-code. Anyway, my solution:

start program:
primes = GetPrimesUnder(2 million) // gets the list of primes under 2 million
return SumOfArrayElements(primes) // sums it up

Extremely inefficient, I doubt you could do up to 2 billion at any reasonable speed

wat

but it didn't ask for 2 billion. Or any reasonable speed.

Yes it's much more efficient to spend days optimizing your algorithm for something that is run once a year when you can get the same result with a 10 liner even if it takes longer to run.

Sieve of Atkin is always slower than an optimized sieve of Eratosthenes(wheel factorization + segmentation for cache speed).

pip install numpy primesieve

import primesieve.numpy
import numpy

step = 10000000

def sumPrimes(n):
psum = 0
i = 0
while i < n:
upper = i+step
upper = n-1 if upper>n else upper
psum += numpy.sum(primesieve.numpy.primes(i, upper))

i += step
return psum

for i in [2000000, 2000000000, 20000000000]:
print 'Sum of primes below {:,}: {:,}'.format(i, sumPrimes(i))

This is so easy LOL
>download a file with X number of primes beforehand
#!/bin/bash
SUM=0
PRIMEFILE="./primes"
for i in $(seq 1 `wc -l $primefile | awk '{print $1}'`);
do
NUM=`head -n $i $primefile | tail -n 1 | awk '{print $2}' | sed 's/,//g'`
SUM=$(expr $SUM + $NUM)
echo sum of first $i primes is $SUM
done
echo final sum is $SUM

Your "sieve" is several orders of magnitude worse than trial division.

There is a paper out there on how to properly sieve prime numbers in Haskell, read it: cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Or just use a vanilla iterative version on arrays. Non-lazy linked lists will automatically kill any advantage of sieves over trial division, you need either random access & mutation, or some form of priority-queue-like lazy merging.

Given an integer x and x > 3, don't you only have to check factors from 2 to sqrt(x) to see if its prime? Also you only have to check odd numbers (except 2) so you can skip every other one. If so, wouldn't that make the program a lot faster?

Doing naive division testing can be done even faster by checking 2 and 3, then only checking 6k-1 and 6k+1 with incrementing k until you reach sqrt(n). See:
en.wikipedia.org/wiki/Primality_test#Simple_methods

The problem with this type of check is that it's too fucking slow for large numbers.

Wow I wasn't even aware of 6k±1, it appears like i was on the right track with the sqrt(n) and i see the issue with very large numbers.

>4 is prime
wew lad

I just rewrote it in python and am running it
at 100k now it is slowwwwwwwww
make one that'll calculate it in less than 10 seconds pls

isPrime n = (==2) . length . filter ((==0) . mod n) $ [1..n]

answer = sum . filter isPrime $ [1..2000000]

Edit:
isPrime n = null . filter ((==0) . mod n) $ [2..n-1]

4 is a transprime number.

Don't oppress it you SHITLORD

...

I wrote one that is fast as fuark, but it's in c so...

No you didn't.

>can't implement a bubble sort or calculate prime numbers
how the fuck did this guy land an interview in the first place?

what kind of hackery is this ? is that python?

>posting in these threads without sage
>not reporting these threads
It's like you all want Sup Forums to be more shit than it has to be

how long does this take to run?

30 seconds on my shitty 8 year old AMD cpu.

Do people actually ask this in real life? The biggest technical question I got was ol' FizzBuzz for my Junior SE job that I got right out of college that I'm still at. Maybe because it's a non tech company

from math import sqrt
from time import time
max_n = 2000000

def is_prime(n):
for i in range(2, int(sqrt(n))+1):
if (n%i) == 0:
return False
return True

def sum_primes(max_n):
psum = 0
for i in range(2,max_n+1):
if is_prime(i):
psum += i
return psum

niggers = time()
print(sum_primes(max_n))
print(time()-niggers)

for max_n = 2000000
142913828922
33.94594144821167

i'm running the 2 billion right now, but it's pretty clear it's going to take too long.

use a sieve.

new and improved
#ORIGINAL CODE DO NOT STEAL
from math import sqrt
from time import time
max_n = 2000000

def find_primes(n):
primes = [True]*(n+1)
for i in range(2, int(sqrt(n))+1):
if primes[i]:
for j in range(i**2, n+1, i):
primes[j] = False
return primes

def sum_primes(max_n):
primes = find_primes(max_n)
psum = 0
for i in range(2,max_n+1):
if primes[i]:
psum += i
return psum

niggers = time()
print(sum_primes(max_n))
print(time()-niggers)


for max_n = 2000000
142913828922
0.9490542411804199

i only have 3gb of memory so i can't run the 2 billion and 20 billion cases kek. someone will have to help me out with those.
MemoryError

use a segmented sieve.

for(var i = 1; i

for(var i = 1; i

lmao
someone put this in the CS grad macro

gcc yourshitprogram.c wew lad so hard

>uses 20gb of ram
jesus christ dude

not gonna run that shit rofl
thought my computer exploded

unused ram is wasted ram tho

>20 billion
eh, this is too tacky since the sum would be beyond the 64-bit limit so you'd have to carry the sum every time.

with my python code and amount of ram i was able to run 200 million which took almost 2 minutes. 20 billion should take about 200 minutes.

My C++ code can do 2 billion in about 8 seconds. 20 billion would probably be 8*10*2*2 seconds (320 seconds).

I'll run it and print out the hexadecimal representation.

Real world solution here kek

here you go op it took me 2 hours

primes = ()

for i in range(1,2000000,1):
isPrime = True
division_result = float(i)/float(2)
# checking if number can divide into 2 without any decimals
if not (division_result - int(division_result)) == 0 or i == 2:
division_result = float(i)/float(3)
# checking if number can divide into 3 without any decimals
if not division_result - int(division_result) == 0 or i == 3:
# check every number if its not 2 or 3
for j in range(1,i,1):
if not i == 1 and not j == 1:
if not i == j:
division_result = float(i)/float(j)
if division_result - int(division_result) == 0:
isPrime = False

if isPrime:
print i
prime = ()
prime = prime + (i,)
primes = primes + (i,)
else:
isPrime = False
else:
isPrime = False

for i, prime in enumerate(primes):
print primes[i]

Haha holy shit this actually works, although it maxxed out the python limit for a single process.

Why not using range(3,2000000,2) ? This will save you half of your iterations, which means it's 100% faster than before..
All you have to do is init the prime sum with 2.

Also for j in range(1,i,1) is not good, you only need to search until the squareroot of i.

Why?
Let's say we are looking wether N is prime or not. Let A be a number bigger than the square root of N.
Let's assume N = A * B, then B has to be smaller than the square root of N (since A is bigger than the square root, every bigger B would result in something biggern than N). But than we would have noticed N can be divided by B. So we only need to check until the squareroot of N.


Not that it matters, your performance will be terrible with python..

Honestly, it was just a joke. It was the worst way I could think of when still correctly meeting the criteria.

and what is the "best" way to solve this

Here's some c++ code to start with
const std::size_t PrimesUpperBound{ 1000000 };
const std::uint_least64_t RangeEnd{ 2000000 };
std::vector primes{ 2 };
primes.reserve(PrimesUpperBound);

for (std::uint_least64_t n = 2; 2

prime*prime > n
Oops

Oh ffs
Yeah you have to check all the primes in the vector and make sure they don't divide the next number you're considering

Shut up, James. You sodomite.

Wats r prim?

heehee

how much u think it'll take in the end?

2 billion

python prime.py
95673602693282040
886.389775038

I started playing with it in java and ended up with such a fucked up spagetti code I think I will continue with it and post it just for entertainment.
Spoiler: multi-threading involved.

kek nice

i might try modifying it into a segmented sieve later today, but it will make it slower.

LOOK Sup Forums IT'S MEEE GIVE ME ATTENTION. I'M A LAME ASS BITCH WHO USES A NAME ON Sup Forums HAHAHAHA B-B-B-B-B-B-B-BUT YOU GUYS ACCEPT ME R-R-R-R-R-RIGHT.

haha u mad

Just filter them. If they want to roleplay like they're on reddit they can get shadow banned like they're on reddit.

Done yet?

I can do you one better. I can sum all primes up to infinity:

-1/12

See: Just do
sum(primes(2000000000))
and
sum(primes(20000000000))

section .bss
lim equ 20000000000
b resb lim/8+1

section .text
_start:
mov rdi, lim
xor edx, edx
mov ecx, 2
.l:
add rdx, rcx
mov rax, rcx
.l1:
cmp rax, rdi
jnb .l2
bts [b], rax
add rax, rcx
jmp .l1
.l2:
inc rcx
bt [b], rcx
jc .l2
cmp rcx, rdi
jb .l

; rdx = answer


ez pz. 20 billion takes 2.2 GB, ~3 min

such a good thread

The best way is to just import someone else's code to do it for you.

completes all three sums in 30 seconds with only 10mb of memory usage.

+1, I am dying here

Pajeet pls go. Are you going to import people's modules on a white board or in coding challenges? By the same logic why even write code? I can use wolfram alpha and get an answer in about a second.