FizzBuzz is pie, forget about it

Can Sup Forums solve simply problems like pic related in efficient manner of implementation?

Other urls found in this thread:

primes.utm.edu/lists/small/1000.txt'
primes.utm.edu/lists/small/millions/
twitter.com/SFWRedditGifs

Eratostenes until 2 million using an accumulator

This. Sieves are not complicated.
/thread

Can you implement that off the top of your head on a whiteboard?
I just finished mine, took me ~25 minutes:
limit = 2000000 # The limit to check for primarity
intList = set(range(3, limit + 1, 2))
PRIMES_SUMMED = 2
while True:
n = 2
p = intList.pop()
PRIMES_SUMMED += p
if p**2 < limit:
while n*p

{ echo 0 ; /usr/games/primes 2 2000000 | sed 's/$/+/' ; echo 'p' ; } | dc

>import the primes in python
>sum them

>importing ANYTHING
gitgud m80

>Algorithm for Sup Forums

"Find the solution of this problem"
>import solution
HIRED :^)

>while true
>break

ewwwww

Literally nothing wrong with it, and you can't prove otherwise. Other option is making a generator and raising a stopiteration flag.

lost

when did Sup Forums stop basic logic ?

>popping elements out of a set in a particular order

Did this and its taking forever.
Fucking kill me

def isPrime(n):
for ii in range(2, n-1):
if( !(n % 2) ):
return False
return True

def sum_all_primes_below(n):
psum = 0
for ii in range(2, n-1):
if( isPrime(ii) ):
psum += ii
return psum

print( sum_all_primes_below(2000000) )

Guys, your algorithms are quadratic time.

>calling primality "primarity"
>checking 2000000 even though the problem clearly states "_below_ two million" plus the number obviously isn't prime anyway
>naming a set "list"
>using camel case
>using all-uppercase for non-constant
>while True ... break

>is_prime() returning true for nchecking if n%i for every odd value of i
>while i

>>checking if n%i for every odd value of i
fuck, I meant even, obviously

it's still running

OK, I'll dig up my old archive.
i64 run( i64 n) {
i64 res = 2;

for( i64 i = 3; i < n; i += 2) {
if( isPrime(i) )
res += i;
}

return res;
}

bool isPrime( i64 n) {
if( n % 2 == 0) return false;
i64 asqrt = (i64)ceil( sqrt( (double)n));

for( i64 i = 3; i

public class Problem10 {

public static void main(String[] args) {
boolean[] primes = getPrimesEratosthenes(2_000_000);
long sum = 0;

for (int i = 0; i < primes.length; i++) {
if (primes[i]) {
sum += i;
}
}
System.out.println("Sum: " + sum);
}

public static boolean[] getPrimesEratosthenes(int k) {
boolean[] primes = new boolean[k];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;

for (int i = 2; i * i < primes.length; ++i) {
if (primes[i]) {
for (int j = i * i; j < primes.length; j += i) {
primes[j] = false;
}
}
}
return primes;
}

}

Huh? set.pop() will remove and return the smallest hash of the set, at least in CPython.
This doesn't generate primes. You're understanding of primes is wrong: all primes are uneven, but not all uneven integers are primes. isPrime will not always return a prime, and is in fact moot, since you could just make iterate in increments of 2, e.g. for ii in range(3, n-1, 2) for the same effect.
>even though the problem clearly states "_below_ two million" plus the number obviously isn't prime anyway
Exactly, since it isn't prime, it doesn't contribute to the output, and only adds one single extra instance to the sieve total.
>while True ... break
What's wrong with this, actually?

rate my retarded meme

char[2000000] fag;
int total;
for (int i = 0; i < 2000000; i++)
{
fag[i] = 1;
}
for (int i = 0; i < 1500; i++)
{
for (int j = 2; j < 1500; j++)
{
fag[i*j] = 0;
}
}
for (int i = 0; i < 2000000; i++)
{
if (i == 1)
total += i;
}
[/code

Shit yeah I fucked that up

>Can you implement that off the top of your head on a whiteboard?
Any semi-competent programmer can.

Is python really that slow? My javascript version finishes instantly

function isPrime(num) {
let start = 2;
while (start 1;
}

function primeRange(min, max) {
let primes = [];
while (min < max) {
if (isPrime(min)) {
primes.push(min);
}
min++;
}
return primes;
}

primeRange(0, 2000000).reduce((sum, i) => sum += i);

>instantly
No, it doesn't. And 2M is still a small number to brute force with trail division.
This finishes in ~23s on my X220:
primes_sum = 2
for i in range(3, 2000000, 2):
if not any(i % ii == 0 for ii in range(2, int(i**0.5) + 1)):
primes_sum += i
print(primes_sum)
vs sieve implementations, which are < 1s.

I'm not solving Project Euler for you

Can I just keep all the primes in a data table instead of calculating them? You know, for speed?

>Can I just keep all the primes in a data table instead of calculating them?
Like a rainbow table for primes?

I timed my javascript and it's 523.467ms

int i = 1
int k = 1
int x[]
while i

fuk i messed the last line, w/e

Easy:
int isPrime(int i)
{
for(int j = i;j > 1;j--)
{
if(i % j == 0 && i != j)
return 0;
}
return 1;
}

int main(int argc, char *argv[])
{
int endSumming = 20;
int sum = 0;
for(int i = 2;i < endSumming;i++)
{
if(isPrime(i))
sum += i;
}
printf("%d\n",sum);
return 0;
}

I tried it the normal way but I got bored of waiting for it to finish so I looked up that prime sieve.

#include
#include
#define LIMIT 2000000

int main(void)
{
char *a = (char *) calloc(LIMIT + 1, sizeof(char));
size_t i, j, sum = 0;
for (i = 2; i

Why are everyone set i from 0 to n ?

You can go to sqrt(n), it's the same guys.

programming is about cluing together libraries other people wrote. We don't live in the 80th anymore.

do {

} while (condition) is better, right?

Actually, checking if i*i

here's an implementation in C99/OpenMP

because who needs efficient code when you can always throw moar cores at the problem

#include
#include
#include
#include
#include
#include

uint64_t add_primes_under(uint32_t n)
{
uint64_t acc = 0;
uint32_t sqrt_n = sqrt(n);
bool * prime;

prime = (bool *)malloc(n * sizeof(bool));

for(uint32_t i = 0; i < n; i++)
{
prime[i] = true;
}

#pragma omp parallel for
for(uint32_t i = 2; i

iterate until two million
if number is prime add to accumulator
end

Bretty gud

>is prime
i mean, you're not wrong

>no one uses multithread to speed up the process

This person is:

extern crate primal;

fn sum_of_primes(below: usize) -> usize {
let sieve = primal::Sieve::new(below + 1);

(1..below).filter(|&n| sieve.is_prime(n)).sum()
}

fn main() {
println!("Below 10: {}", sum_of_primes(10));
println!("Below 2 million: {}", sum_of_primes(2_000_000));
}

Y`ALL SUCK

a=0
for i in `curl 'primes.utm.edu/lists/small/1000.txt' | sed 24q | tail -n20`; do
a=$((a + i));
done
echo $a

Pretty cute.

How about 2,000,000,000? Mine did it in 27 sec. Though at ~95*10^15, it might've overflown.

because you cant faggot

>he doesn't have arbitrary-precision data types

I just downloaded the list from here and summed it in excel. Took less than 30 seconds.

primes.utm.edu/lists/small/millions/

The answer is 142913828922

>not using binary quadratic forms
LEL

With my solution, 200,000,000 requires 191MB of memory
2,000,000,000 requires 1.5GB memory and the swapping becomes a much larger operation than the prime calculations.

The solutions already exist on the website. Not to mention there are countless solutions and explanations on the web. It's not as if OP is asking you to do his HW.

>The solutions already exist on the website

you can only see them until after you have solved the problem.

that's true. but if they wanted to test for that they would give you something non trivial to piece together. its not the objective of the exercise.

>you can only see them until after you have solved the problem
I'm going to assume that that's not actually the case and you're just awful at English.

use a bit set to cut the memory usage to 1/8th.
only bother with odd numbers to cut it down to 1/16th
only bother with digits ending with 1,3,7 and 9 to cut it down to 1/20th the size.

Thus, 2 billion should only require ~100MB of memory.

(Of course you need to account for 2,3,5 being primes so start your testing at 7)

kys faggot

Okay, so I was right.

Why is no one keeping a list with all found prime numbers and then running over that list to check if the next number is also a prime?
Why would you run over every single number.
There's no point in running over all even numbers if you know the number isn't divisible by 2.
Neither is there a point to running over all multiples of 3 after you find out it's not divisible by that. This goes on for every single prime.

Rolf g really doesnt know how to code...

whant language is that?
haskell?

on line 6, should it be?
p = intList.pop(n)

youre poping the first element, so no argument pops the first?

BUT WAIT is it trivial that all non-primes between:
prime A < non-primes < prime B
are multiples of primes smaller than B ?

If you read the thread, there are multiple "correct" implementations doing what you suggest, including sieves.
>haskell
It's Python.
>so no argument pops the first
For set.pop(), it takes no arguments and an "arbitrary" element is removed (since sets aren't ordered), which ends up being the smallest hash of the set.
>is it trivial that all non-primes between:
>prime A < non-primes < prime B
>are multiples of primes smaller than B
I'm not sure actually.

expensive but
>for x in 0..2000000
>> if (factor x).count == 1
>>> n +=x
>print(n)

I tried implementing this last night and it didn't really work.

What I understood is you get the numbers 2, 3, 5, and 7. and eliminate all multiples of these numbers down the the list from 2 to n in a huge lookup table and then add all the untouched values?

laugh at me
#!/usr/bin/python
import subprocess
primes = 1
for x in range(1,2000001):
s = subprocess.check_output(['factor', str(x)])
t = s[(len(str(x))+2):]
u = t[:-1]
try:
if (int(u) == x):
primes+=x
except ValueError:
pass

print(primes)

I'll tell you when it's done, my laptop is taking a while with it

let is_prime n =
let rec divisors_count count d =
if d > n then
count
else
let count =
if n mod d = 0 then
succ count
else
count in
let d = succ d in
divisors_count count d in
let count = divisors_count 0 1 in
count = 2
;;

let sum_primes limit =
let rec compute_sum sum n =
if n = limit then
sum
else
let sum =
if is_prime n then
sum + n
else
sum in
let n = succ n in
compute_sum sum n in
compute_sum 0 0
;;

let time limit =
let begin_time = Sys.time () in
let sum = sum_primes limit in
let time = Sys.time () -. begin_time in
Printf.printf "%d,%d,%f\n" limit sum time
;;

let () =
let limit = Sys.argv.(1) in
let limit = int_of_string limit in
let sum = sum_primes limit in
let sum = string_of_int sum in
print_endline sum
;;

>you get the numbers 2, 3, 5, and 7
For each prime p, you mark multiples of p starting from 2p. The next smallest number from p is a prime, and repeat, up to p < sqrt(n) for which n is the limit you wish to find primes in. So yes, 2, 3, 5, and 7 are primes, but you would continue if 7 < sqrt(n) and only then would unmarked values be primes. There are various ways to implement with varying optimizations. Obviously if you're using a set or array from the range of n, then your limit will not be n but memory required to hold the set/array.
Neat. But terribly unoptimized, given that factor is intended for prime factors, and that you iterate through the entire range when the uneven range would suffice. A simply brute force implementation is

>use all primes up until sqrt(n)

This really does sound like a chicken and the egg problem.
I need a number primality test before I can write a prime number sieve?

public override void Run()
{
long result = 0;
List PrimeList = new List();
for(int i = 2; i < 2000000; i++)
{
if (isPrime(i))
PrimeList.Add(i);
}

foreach (var n in PrimeList)
result += n;

Console.WriteLine(result);
Console.ReadLine();

}

private bool isPrime(long n)
{
for (int i = 2; i

>isPrime
camelCase foe method in C#

>I need a number primality test before I can write a prime number sieve?
No, because the sieve finds primes for you. You start from 2, because 2 is prime. And since 2 will only eliminate even multiples, and even integers are not prime, you can start from 3 and list only odd numbers. Multiples of 3 will mark 6, 9, 12, etc, and the next unmarked number is 5, a prime. Repeat.
You don't go higher than sqrt(n), because the sieve would be repeating itself for the same reason going higher than sqrt(8) for pair factors of 8 repeats, e.g:
8 / 1 = 8 * 1
8 / 2 = 4 * 2
8 / 3

Just to be sure, I'm not doing anything redundant with this implementation, right?

int is_prime(size_t n)
{
size_t sq = sqrt(n);
if (n < 2)
return 0;
else if (n == 2)
return 1;
size_t i;
for (i = 3; i < sq; i += 2)
if (!(n % i))
return 0;
return 1;
}

int main(void)
{
char *a = (char *) calloc(LIMIT + 1, sizeof(char));
size_t i, j, sum = 0, sq = sqrt(LIMIT);
for (i = 2; i < sq; i += (i > 2) ? 2 : 1)
if (is_prime(i))
for (j = i * 2; j < LIMIT; j += i)
a[j] = 1;
for (i = 2; i < LIMIT; i++)
if (!a[i])
sum += i/*, printf("%zu\n", i) */;
printf("%zu\n", sum);
free(a);
return 0;
}

>>using camel case


>not Using Camel Case

is_prime(47);


>slightly less shitty

>doesn't work

if (i == 1)
total += i;

Did you mean:

if ( fag[i] == 1)
total += i;

public class HelloWorld
{

public static void main(String[] args)
{
long s = 0;
System.out.print(2 + "" +3);
for(long i=1;i

const upperLimit = 2000000

let sieve = new Set(Array.from(Array(upperLimit - 2), (_, i) => i + 2))
sieve.forEach((e) => {
let toRemove = 2 * e
while (toRemove < upperLimit) {
sieve.delete(toRemove)
toRemove += e
}
})

const sum = [...sieve].reduce((a, b) => a + b)
console.log(sum)


Pretty easy, desu

>>notUsingCamelCase

>doesn't recognize the most classic primality check algo there is
>claims it doesn't return true for 47
check your glasses

>only bother with digits ending with 1,3,7 and 9 to cut it down to 1/20th the size.
Is there a way to implement this that doesn't too complicated and/or expensive (divisions)? It's easy to get rid of even numbers, but I'm not sure how to do get rid of 5|n...

Using a reverse radix tree?

Where did I go wrong? Getting 1179908154 as the output.
int main() {
int MAX = 2000000;
int total = 0;

std::vector v;
for (int i = 0; i < MAX; i++)
v.push_back(false);

if (MAX >= 2) {
for (long int i = 2; i < MAX; i++) {
if (v[i] == false) {
total += i;
for (int j = i; j < MAX; j += i) {
v[j] = true;
}
}
}
}
std::cout

>int MAX
>not static const constexpr max

int overflow in total.

>const constexpr
kek

This.

Bad habit from my last job where the guy I was working under used a gross mix of Java and Javascript naming schemes.

Trivial for a Ruby Code Artisan™ such as myself.

require 'prime'

puts Prime.each(2000000).reduce(:+)

anyone have the answer to the total?

Run any of the programs in this thread you lazy bastard.

how do I know any of them are actually correct?

How do you know there is such a thing as truth?

someone already posted it you fucking retard

are you the pajeet from

17, the sum of all primes below 10. Answer should be the same regardless of limit to test to.

//this takes more than 5 mins and doesn't return the correct number
//due threads running on different cores can't always run the correct value of pri
//the thread sometimes read the dirty value from the cache just often enough to be off slightly
static void Main(string[] args)
{
List primes = new List();
int max = 2000000;
primes.Add(2);
for (int i = 3; i < max; i += 2)
{
bool pri = true;
Parallel.ForEach(primes, (p) => { if(pri) pri = i % p != 0; });
if (pri) { primes.Add(i); }
}
primes.Add(1);
decimal total = 0;
primes.ForEach((p) => total += p);
Console.WriteLine(total);
}

static void run() //this takes 46 seconds
{
List primes = new List();
int max = 2000000;
primes.Add(2);
for (int i = 3; i < max; i += 2)
{
if (primes.TrueForAll((p) => { return i % p != 0; }))
primes.Add(i);
}
primes.Add(1);
decimal total = 0;
primes.ForEach((p) => total += p);
Console.WriteLine(total);
}
This was fun in a way. The overhead of TPL when doing something like this is insane, I can't even imagine how slow it would have been with a lock too. The parallel implementation was using all 16 threads from my CPU at about 90% each too.

haskell would be
sum [x | x

>threading for one small function
>complains about overhead

If you want effecient multithreading, you give it workloads.

Each thread handles n/t numbers (so if i'm doing 1000 with 10 threads then i have each thread doing 100 t0:0->99, etc.,

Of course you can't do parallel for each then, well not as easily...

Also out of curiosity, can you build this using nothing but Linq via Enumerable.range, where, and select?

is total uninitialized?