Asked to sum all prime numbers under two million

>asked to sum all prime numbers under two million

Other urls found in this thread:

github.com/alex47/PrimSumCalc
en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests
en.wikipedia.org/wiki/Primality_test#Pseudocode
twitter.com/SFWRedditGifs

yeah that's easy lmao
what are you some sort of dumbass

int total = 0;
for(int x = 0; x < 1000000; ++x){
for(int y = 0; y < 1000000; ++y){
if(x % y == 0){
for(int z = 0; z < x; ++z){
++total;
}
}
}
}

Now do it in QBASIC

I wrote. 20,000 line divine intellect compiler that operates just in time and ahead of time. You seem to be in denial, why don't you download my two meg distribution and you can use my fuckin compiler. You're a nigger, you're a fuckin nigger.

this is identical to javascript in almost every way.
Just saying :)

Why did you do that fugly loop with z? Why not just add x to the total?

>In less than a second.

It's real easy.

SIEEEEEEEEEEEEEEEEEEEEEEEVE

>an incredibly basic function will look pretty much the same no natter what language or syntax is used
rally naek mi thnk

i am mentally challenge. can you explain your code?

pls

unless they allow you to look up methods to check for primes, what can they legitimately expect from you other than checking whether the number is even and larger than 2, and then running a loop that checks the modulus of all the numbers up to half the the original number. it will be slow as shit, but it is guaranteed to work.

Use a sieve.

>up to half the the original number.

You only need to check up to the square root. For every divisor less than the square root there's a corresponding one above it. If a number doesn't have a divisor less than or equal to its square root it's not gonna have any above it.

package main

import (
"fmt"
"primes"
)

func main() {
result := 0
seq := primes.NewSequence(2)
for i, p := range seq.Next() {
if(i == 2000000) {
break
}

result += p
}
fmt.Println(result)
}

#include
#include

#define SIZE 2000000

void sieve(char *primes, int size){
int sqr = (int) sqrt(size);
for(int i = 2;i

>google "list of prime numbers"
>copy paste the ones below 2 million
>declare an array with those primes in your program
>it only has to sum every part of the array in one cycle and return the value
fast as fuck

#!/usr/bin/python3

import math
n = 4*(10**6)
primes = []

def get_primes(n):
sieve = [False] * n
primenumbers = []
i = 2

for i in range(2, n):
if not sieve[i]:
primenumbers.append(i)

for j in range(i*i, n, i):
sieve[j] = True
return primenumbers

primes = get_primes(n)
sum = 0
for prime in primes:
sum += prime

print(sum)


544501644261

woops. That was the wrong limit. The correct sum is: 142913828922

What's the point of your thread, ausist?

>copy paste
>not making your program search the web and download the data-set
What are you a fucking monkey

This segfaults.

gcc -o fuckpython fuckpython.c -L/usr/include/math.h -lm

segmentation fault

>using import math

>++total
What does that line do?
Shouldn't it be something like
total+= z?

I compiled it and I don't get segmentation fault.

How did you compile it?

...

Use MATLAB.

This is retarded

X and y are always the same

So x%y ==0 is always true

But z is always =x

#include

int main() {
uint primesum;
for (int i = 0; i < 2000000; i++)
{
if (checkPrime(i))
primesum += i;
}


ez

is this matlab?

long sum;
for(int i = 0; i

syntax aside. This checks out.

This is expensive.

Explain

2 million divisions by 2. On cpu's that have division on chip as an instruction.

Would love to see the benchmark. Guessing ms
>not exactly expensive

Would like to see your better approach.
> I'm not btw

comyydy gold lad

maybe 30 years ago when CPUs weren't preloaded with division and would do it by addition yeah

type ('state, 'a) stream =
{
state : 'state;
generate : 'state -> 'state * 'a;
}
;;

let mk_stream state generate =
{
state = state;
generate = generate;
}
;;

let filter p stream =
let state = stream.state in
let rec generate state =
let state, n = stream.generate state in
if n mod p = 0 then
generate state
else
state, n in
mk_stream state generate
;;

let sieve stream =
let state = stream in
let generate stream =
let state, p = stream.generate stream.state in
let stream = { stream with state = state; } in
let stream = filter p stream in
stream, p in
mk_stream state generate
;;

let numbers =
let state = 2 in
let generate state = succ state, state in
mk_stream state generate
;;

let primes = sieve numbers;;

let next stream =
let state, x = stream.generate stream.state in
mk_stream state stream.generate, x
;;

let main () =
let rec loop sum stream =
let stream, p = next stream in
if p < 2_000_000 then
loop (sum + p) stream
else
sum in
let sum = loop 0 primes in
print_endline (string_of_int sum)
;;

let () = main ();;

result

~$ time ./prime
142913828922

real 7m5.209s
user 7m5.147s
sys 0m0.027s

r8 and h8

github.com/alex47/PrimSumCalc

int sum = 0;
for (int cand = 0; cand

Yep that will use 2Mb of memory and is actually pretty fast.

Fuck I did odd not prime but whatever I'm going to bed

>this checks out
my man it does not

Exception in thread "main" java.lang.ArithmeticException: / by zero

WTF is this, do you even do math?

This

>not understanding how for loops work

>every odd number is a prime
kek
terrible. also what is overflow?

What the fuck? That's slow as fuck.

For mine ( ) I get:
time ./primes.py
142913828922

real 0m0.464s
user 0m0.448s
sys 0m0.012s

>What the fuck? That's slow as fuck.
Poorly coded.

But how long does it take to calculate the sum 9,6Mhz and only 1k flash?

Gotta do some sport first though. BUT WE WILL GET THERE

You could generate primes with a true sieve of Erathostenes, then just sum them.

(For huge numbers there are of course better algorithms than the Sieve of Erathostenes - how much does this need to scale?)
import scala.annotation.tailrec
import scala.collection.parallel.mutable

def sieveOfEratosthenes(limit: Int) = {
val (primes: mutable.ParSet[Int], sqrtLimit) = (mutable.ParSet.empty ++ (2 to limit), math.sqrt(limit).toInt)
@tailrec
def prim(candidate: Int): Unit = {
if (candidate

-L is for adding to the library search path, -I is for adding to the header search path.

In a sane installation,
gcc -o fuckpython fuckpython.c -lm
should work just fine.

can anyone beat my time?

I'm using

How much RAM? I doubt you can hold all the 2 million bits (250 kB in packed form) for a sieve.
All you need for testing every odd number larger than 2 somewhat fast is storage for all primes under floor(sqrt(2000000))=1414, which comes out to 446 bytes in 16-bit integers.

haskell

solution = sum $ takeWhile (

Yeah the sieve does not work. Maybe if I sum them prime by prime. Walking through without a sieve.
But too lazy right now.

Lel, functionalets
's sieve code runs in 120 ms (compiled statically, because the dynamic loader can add about 0.2 seconds with a shitty SD card) on an original Raspberry Pi with default 700 MHz clock (change "sum" to long long resp. "%lld" in output), in about 10 ms on a cheap-ass 3.1 GHz VPS.

That's what I meant. But instead of testing every number x by dividing by every possible prime factor (3, 5, 7, 9, …) smaller than sqrt(x), you're keeping a list of all primes smaller than sqrt(N) that you have found, which should accelerate things once you test integers larger than ~1000.

That still doesn't work out well if you have less than 512 byte of RAM (that spec sheet only talks about size of Program Flash and Data EEPROM) or only a 8-bit microcontroller.

I don't know why but it still segfaults.

Is there any clever way to figure out if a number is prime?

literally no

>==0
Kys

You can win a prize if you find the next highest prime number. Good luck. People actually attempt this.

numbers = 1:1999999;
primesIndices = isprime(numbers);
primes = numbers(primeIndices);
primeSum= sum(primes);

en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests

Yes, but some of them rely on theorems that haven't been proven yet, also their computational effort (a lot of code and a lot of possible bugs) isn't worth it over the naive approaches for such relatively small numbers.

>average java programmer

long SUM = 0;

for (int i = 0; i

Moved up from a attiny13 to atmega8a.

calculated the sum of primes below 200000.
2 million would have caused an overflow as I figured.
This took a few minutes though, because I haven't implemented the sieve.
Will now try to fix the overflow and implement a sieve. Not sure if it fits on an atmega8a, but should be possible

fuck. Forgot photo.

From math import sumprimesunder

return sumprimesunder (2000000)


Suck it, gaymos

data = read.csv ("savedprimes.csv")
for i in data:
sum+= i

With a compiler.

Really? I thought I needed to use a cork-screw!!
Still, I got a segfault. I don't know why.

> return false return true
> Not using ternary operator on numtoAdd
> Qt
> using namespace std;

lel

I had the wrong number in #define. It works.

>> return false return true
whats wrong with this?
>> Not using ternary operator on numtoAdd
I don't know what this is
>> Qt
there is literally nothing wrong with Qt
>> using namespace std;
I'm not typing std:: before every single thing in cout and cin

If you're just doing a naive division test, you can speed it up 3x. See:
en.wikipedia.org/wiki/Primality_test#Pseudocode

>asked to sum all prime numbers above two million

>generate all multiples of 6 under 2 million
>check every number one higher and lower than each for primality
>add found primes

Am I doing this right?

ok I looked up stuff and improved it based on your comments and some algorithm
how about now

import math

def checkprime(integer):
root = math.sqrt(integer)
j = int(math.floor(root))
if root == j:
return False
else:
for i in range(j):
if i > 1:
if integer % i == 0:
return False

return True

primes = [1,2,3]

i = 6
while i < 2000000:
if checkprime(i-1):
primes += [i-1]
elif checkprime(i+1):
primes += [i+1]

i += 6

print sum(primes)

I get 129230485919 as result

The proper implementation shown below is O(n), amortized.

#include
#include

int main(int argc, char* argv[]){

if (argc != 2){
return 1;
}

int n = atoi(argv[1]);
bool* bools = new bool[n];

bools[0] = true;

for (uint i = 2; i

> 129230485919 != 142913828922

The answer is 142913828922

I noticed that. However, I can't notice where I made the major errors in my program

Why stop there? Why not sum all the prime numbers?

The error is that the logic of using increments of 6 is wrong.

Sieve of Erathostenes, for example.

But every prime number is one below or above a multiple of 6.

>But every prime number is one below or above a multiple of 6
what

Besides 2 and 3, this holds true for every prime number possible. If you're writing primality tests, you should probably know about that.

Being +/- 1 from 6*n does not imply primality.
Being prime implies being +/- 1 from 6*n.

A -> B =/= B -> A

So, how do you actually prove that your answer is correct without relying on another computer program which similarly can't prove that it's actually correct?

By formally proving the correctness of your algorithm.

>Being prime implies being +/- 1 from 6*n.
And hence, not being +/- 1 from 6*n implies not being prime.
Therefore, it is only necessary to check 6*n +/-1 for primality.

oh my god
this actually works

It could be the case that for some i, 6*i - 1 and 6*1 + 1 are prime.
Your program will only add 6*i - 1 to the sum.

Haha. That's cute :)