FizzBuzz is pie, forget about it

Eratostenes until 2 million using an accumulator

>>59516834
This. Sieves are not complicated.
/thread

>>59516834
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 <= limit:
            intList.discard(n*p)
            n += 1
    else:
        PRIMES_SUMMED += sum(intList)  # It's assumed only primes remain
        break
print(PRIMES_SUMMED)

>>59516874
I never said they were, but it's much harder than fizzbuzz, which just takes simple logic to implement. But so why does /g/ meme about fizzbuzz when you should really be learning algorithms?

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

>import the primes in python
>sum them

>>59517442
>importing ANYTHING
gitgud m80

File: fountain.jpg (5KB, 200x140px) Image search: [Google]

5KB, 200x140px

>>59517442
>Algorithm for /g/

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

>>59517030
>while true
>break

ewwwww

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

File: windows_aesthetic.jpg (250KB, 1536x1152px) Image search: [Google]

250KB, 1536x1152px

>>59517556
lost

when did /g/ stop basic logic ?

>>59517030
>popping elements out of a set in a particular order

File: fuck.png (9KB, 388x501px) Image search: [Google]

9KB, 388x501px

Did this and its taking forever.
Fucking kill me

>>59516680

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

>>59518147
>>59518360
Guys, your algorithms are quadratic time.

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

>>59518147
>is_prime() returning true for n<=1
>checking if n%i for every odd value of i
>while i<n instead of i*i<=n

If you don't want to use a sieve, here's a slightly less shit primality check:

#include <stdbool.h>

bool is_prime(int n) {
    if(n<=1) return false;
    if(n<=3) return true;
    if(n%2==0 || n%3==0) return false;
    for(int i=5; i*i<=n; i+=6) {
        if(n%i==0 || n%(i+2)==0) return false;
    }
    return true;
}

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

File: comp sci degree.png (35KB, 654x702px) Image search: [Google]

35KB, 654x702px

>>59518402
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 <= asqrt; i += 2) {
            if( n % i == 0)
                return false;
        }
        return true;
    }

Clearly didn't put much effort into this one, but whatever.

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;
    }

}
 

>>59517894
Huh? set.pop() will remove and return the smallest hash of the set, at least in CPython.
>>59518360
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.
>>59518527
>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

>>59518747
Shit yeah I fucked that up

>>59517030
>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 <= Math.sqrt(num)) {
        if (num % start++ < 1) {
            return false;
        }
    }
    return num > 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);

>>59518883
>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?

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

>>59519381
I timed my javascript and it's 523.467ms

int i = 1
int k = 1
int x[]
while i<2000000
{
for j=0,j<k,j++
{
if i % x[j] = 0
{
k = k+1
x[j] = i
}}}

something like that

>>59520904
fuk i messed the last line, w/e

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

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 2000000

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

File: maths.jpg (12KB, 284x177px) Image search: [Google]

12KB, 284x177px

Why are everyone set i from 0 to n ?

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

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

>>59517506
do {

} while (condition) is better, right?

>>59522681
Actually, checking if i*i<=n a bunch of times in a for(i...) loop is much less expensive than calculating sqrt once for most n's.

>>59522949
Sure, but if you have no skills to review those libraries and understand how and why they work, you're just a monkey with a bunch of random black boxes that you can only hope will work together.

Take the example above. Noone's going to re-implement sqrt() function ever, but if you understand how to do that, you also understand why finding a root is computationally expensive and not always the best solution to your problem.

File: more_cores.jpg (183KB, 800x1000px) Image search: [Google]

183KB, 800x1000px

here's an implementation in C99/OpenMP

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

#include <inttypes.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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 <= sqrt_n; i++)
    {
        for(uint32_t j = 2*i-1; j < n-1; j += i)
        {
            #pragma omp atomic write
            prime[j] = false;
        }
    }

    for(uint32_t i = 1; i < n-1; i++)
    {
        acc += prime[i] * (i+1);
    }

    free(prime);
    return acc;
}

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("Usage: %s <num>\n", argv[0]);
    }
    else
    {
        uint64_t num = strtol(argv[1], NULL, 0);
        uint64_t sum = add_primes_under(num);
        printf("Sum of primes under %" PRId64 ": %" PRId64 "\n", num, sum);
    }

    return 0;
}

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

>>59518838
Bretty gud

>>59524255
>is prime
i mean, you're not wrong

>no one uses multithread to speed up the process

>>59524406
This person is: >>59524231

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 'https://primes.utm.edu/lists/small/1000.txt' | sed 24q | tail -n20`; do
    a=$((a + i));
done
echo $a

>>59524573
Pretty cute.

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

>>59519423
because you cant faggot

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

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

The answer is 142913828922

File: yandex.jpg (3KB, 153x123px) Image search: [Google]

3KB, 153x123px

>not using binary quadratic forms
LEL

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

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

>>59528642
>The solutions already exist on the website

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

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

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

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

File: ss56.png (57KB, 1459x741px) Image search: [Google]

57KB, 1459x741px

>>59528699
kys faggot

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

>>59517030
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 ?

File: Sieve_of_Eratosthenes_animation.gif (154KB, 445x369px) Image search: [Google]

154KB, 445x369px

>>59528975
If you read the thread, there are multiple "correct" implementations doing what you suggest, including sieves.
>>59529013
>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.

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

>>59529994
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?

>>59530095
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
;;

>>59530343
>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.
>>59530576
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 >>59519381

>>59531247
>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<long> PrimeList = new List<long>();
    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 <= Math.Sqrt(n); i++)
    {
        if ((n % i) == 0)
            return false;
    }
    return true;
}

>>59531318
>isPrime
camelCase foe method in C#

>>59531289
>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   <----stop here
8 / 4 = 2 * 4
[...]
8 / 8 = 1 * 8

>>59531622
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;
}

>>59518527
>>using camel case


>not Using Camel Case

>>59518527


is_prime(47);


>slightly less shitty

>doesn't work

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

Did you mean:

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

File: 1484411861975.png (9KB, 239x211px) Image search: [Google]

9KB, 239x211px

public class HelloWorld
{

public static void main(String[] args)
{
long s = 0;
System.out.print(2 + "" +3);
for(long i=1;i<10;i++){
if(i != 1 && i%3 != 0 && i%2 !=0){
s += i;
System.out.print(i);
}
}
s+=5;
System.out.print("sum of primes: " + s);

}
}

>>59516680

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

>>59531796
>>notUsingCamelCase

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

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

>>59532723
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<bool> 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 << "Total sum of primes below "  << MAX << " is " << total << std::endl;
}

>>59533248
>int MAX
>not static const constexpr max

>>59533248
int overflow in total.

>>59533519
>const constexpr
kek

>>59533556
This.

>>59531362
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?

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

>>59533845
how do I know any of them are actually correct?

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

>>59533835
someone already posted it you fucking retard

are you the pajeet from >>59533352

>>59533835
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<int> primes = new List<int>();
            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<int> primes = new List<int>();
            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.

>>59529013
haskell would be

sum [x | x<-[1..2000000], isPrime x]

idk why you guys think this is so hard, shit's easy

>>59534369
>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?

>>59518838
is total uninitialized?

>>59534459
>no one can implement a sieve
>shit's easy

>>59518147
Just off the bat, the for loop in is_prime should be from 2 to sqrt(n).

>>59534482
I know that it would be inefficient to create a thread for every call but I thought having 16x the number of threads doing it would balance it out but clearly it doesn't.

Also a full linq solution is probably possible but since you can't add to the enumerable when you are iterating through it, it will likely require more than 1 line.

haskell saves the day AGAIN

import Data.List

main x = sum $ generatePrimes x

generatePrimes :: Int -> [Int]
generatePrimes bound = generatePrimes' 2 bound [2..bound] []

generatePrimes' place bound remaining primes
    | place >= bound = (place:primes)
    | updatedRemaining == [] = (place:primes)
    | otherwise = generatePrimes' (head updatedRemaining) bound updatedRemaining (place:primes)
    where updatedRemaining = filter (\x-> x `mod` place /= 0) remaining

>>59534900
also i got 1709600813 that right? lel

>>59534937
Total is 142913828922.

>>59534900
>main
please use .

>>59534937
no

>>59534937
No, I'm afraid.

>>59534945
eh my algorithm's right, must be overflowing

import Data.Numbers.Primes (primes)
-- todo, replace with own prime generator

main = (print . sum . takeWhile (< 2*10^6)) primes

>>59534945
The total doesn't matter, because the purpose of such problems is to learn to implement them in code, not chase a solution. This is why importing a list of primes and summing them isn't the right answer, because you may as well not know what a prime is or how to generate them efficiently or not
>>59534975
>doesn't work
>"right"
How so? It's outright wrong, or pseudocode at best

>>59535020
how is the algorithm wrong? just because it doesn't work on my machine for 2 million doesn't mean it's an incorrect algorithm for summing primes below a threshold

>>59532723
>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...
I guess 1/16th should be fine since it doesn't involve n mod 5 (which is expensive I agree).

>>59517506
Yeah I prefer

while not not true:

Rate me

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int main(void){
        int max = 2000000;
        int *nums = (int *) calloc(max + 1, sizeof(int));
        int i, j;
        for(i = 2; i <= sqrt(max); i++){
                if(nums[i] == 0){
                        for(j = i*i; j < max; j+=i){
                                nums[j] = 1;
                        }
                }
        }
        long int sum = 0;
        for(i = 0; i < max; i++){
                if(nums[i] != 1){
                   sum = sum + i;
                }
        }
        printf("%li \n",sum);
}

>>59535199
do it with a bitmap to save memory

>>59535316
New to C, what would the syntax be to create a bitmap. Google is proving useless.

Most efficient solution I can think of. Haven't tested it/run it yet, but it only accounts for odd integers, uses a bitset (std::vector<bool>) and counts as it finds each prime. Doesn't use multiplications or divisions, only possible improvement that is possible is to fix the fact that the square root is evaluated at run time.

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

int main() {
    const int max = 2000000;
    const int sqrtmax = std::sqrt(max);
    std::vector<bool> not_prime((max << 1) + 1);
    const int64_t total = 2;
    //not_prime[0] = true;
    for (int i = 3; i <= smax; i+= 2 ) {
        if (not_prime[(i - 1) >> 1])
            continue;
        total += i;
        for (int j = (i << 1) + i; j < max; j+= (i << 1)) {
            not_prime[(j -1) >> 1] = true;
        }
    }
    for (int i = (smax & ~1) + 1; i <= max; i++) {
        if (!not_prime[(i - 1) >> 1])
            total += i;
    }
    std::cout << total << endl;
    return 0;
}

>>59535436
oh damn, two bugs I just noticed.

int i = (smax & ~1) + 1 finds the nearest odd integer to smax that is above or equal to it. But that means smax may have been added into the total previously. I can't be bothered thinking further about t his so here is a quick solution, leaving the counting to the last part.

Other thing is the count should be incremented by 2. Fixed now.

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

int main() {
    const int max = 2000000;
    const int sqrtmax = std::sqrt(max);
    std::vector<bool> not_prime((max << 1) + 1);
    not_prime[0] = true;
    for (int i = 3; i <= smax; i+= 2 ) {
        if (not_prime[(i - 1) >> 1])
            continue;
        for (int j = (i << 1) + i; j < max; j+= (i << 1)) {
            not_prime[(j -1) >> 1] = true;
        }
    }
    const int64_t total = 2;
    for (int i = 3; i <= max; i+= 2) {
        if (!not_prime[(i - 1) >> 1])
            total += i;
    }
    std::cout << total << endl;
    return 0;
}

>>59535388
I haven't used c in years but bitmaps are not really worth it because its a lot slower but it will mean you don't have to allocate 32bits for each num. I would think you'd be working with something a int with bitshifts while indexing into your memory with j/4.

>>59535436
You got close to reinventing the sieve working on a programming problem on 4chan. That's actually really impressive.

>>59535436
>>59535465
Your implementation sucks and vector<bool> is dumb if you want it to be optimized. Try it with a int array and then your implementation, the array will be faster and use less memory.

>>59535436
>2017
>Still using if statements

File: JA1y4DR.png (308KB, 2056x2089px) Image search: [Google]

308KB, 2056x2089px

>>59535520
>what is cache optimised code
You're an imbecile if you think vector<bool> isn't optimised.

Wait...

>the array will be faster and use less memory.
>use less memory
>32-bit per entry vs 1-bit per entry
Pic related

>>59535567
>Still using if statements
What's wrong with if statements?

>>59535574
You are retarded if you think bools aren't compiled into 32bit on any modern machine, some will compile to 64 bit values on 64 bit compilers.

Which means the overhead of using vector will make you use both more memory and make it harder for the CPU to access the 32bit bools.

>>59535436
2 is prime

>>59522949
check this javascript developer

>>59535642
He increments in 2 from 3, because starting from 2 is pointless because no prime is even

>>59535617
You're clearly just assuming. C++ compilers will optimise the memory space of what are fundamentally arrays. You clearly have no idea about CPU cache real estate.

>>59535617
>You are retarded if you think bools aren't compiled into 32bit on any modern machine
No you're retarded for not reading the ISO standard, vector<bool> is an exception and it's always compiled into a bitset:

>The manner in which std::vector<bool> is made space efficient (as well as whether it is optimized at all) is implementation defined. One potential optimization involves coalescing vector elements such that each element occupies a single bit instead of sizeof(bool) bytes.

This is true in gcc, clang and MSVC.

http://www.gotw.ca/publications/N1185.pdf
http://www.gotw.ca/publications/N1211.pdf

vector<bool> is not a standard template of vector<>

Now please, neck yourself.

>>59535669
Go run your program with max of 2 billion and an equivalent one with a int array and come back and report the memory use and completion time.

Do you realize there is no bools in assembly or are you just that retarded?

>>59535465
There is actually one final optimisation you can make. In the inner loop you can actually start from:

i * i

This is because every composite number would have been already struck out since it would involve prime factors less than i.

        for (int j = i * i; j < max; j+= (i << 1)) {
            not_prime[(j -1) >> 1] = true;
        }

This would make your implementation equivalent to the Sieve of Eratosthenes.

>>59535698
>Do you realize there is no bools in assembly or are you just that retarded?
Do you realise that bool is just a type passed to the compiler which activates a special case of vector rather than a template of it you mongoloid?

e.g vector doesn't have flip() but vector<bool> does.

All compilers will turn vector<bool> into a bitset, i'll even prove it for you in a second.

Why not just return the sum off all primes below 2 million? It is a constant of 142,913,828,922.

>>59535666
You'll totally missed the mark, satan. You're correct but not responding to my statement.
However I see now that my statement was dumb because he -does- begin the counter at 2, therefore including 2 as a prime.
>>59535465
I have one question, why is const int64_t total = 2; "const"? As far as I know it is not a pointer, but a true in-scope variable? Or is total more like an struct with operators than I am realising?

>>59535698
Jee why are you so hostile towards the writer when they are just pointing out your actions?

>>59535721
That is literally valid. But what if I ask you to calculate it? (Hence I'm asking for an action, not a constant number).
You will make a good documentation writer or atleast tester.

>>59517506

limit = 2000000  # The limit to check for primality
intList = set(range(3, limit + 1, 2))
PRIMES_SUMMED = 2
p = 0
while p**2 < limit:
    n = 2
    p = intList.pop()
    PRIMES_SUMMED += p
    while n*p <= limit:
        intList.discard(n*p)
        n += 1
PRIMES_SUMMED += sum(intList)  # It's assumed only primes remain
print(PRIMES_SUMMED)

>>59535741
Oops, not meant to be const, that's an editing error.

>>59535721
Can you or can you not implement a sieve?

File: prime-count.png (247KB, 1310x656px) Image search: [Google]

247KB, 1310x656px

>>59535710
Thanks, this definitely works!

>>59535698
Here it is.

The total for 2 million is

142,913,828,922

The total for 2 billion is

95,673,602,693,282,040

Done in 120mb (~2 billion / 16)

Final code:

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

int main() {
    const int max = 2000000;
    const int smax = std::sqrt(max);
    std::vector<bool> not_prime((max >> 1) + 1);
    not_prime[0] = true;
    for (int i = 3; i <= smax; i+= 2 ) {
        if (not_prime[(i - 1) >> 1])
            continue;
        for (int j = i * i; j < max; j+= (i << 1)) {
            not_prime[(j -1) >> 1] = true;
        }
    }
    int64_t total = 2;
    for (int i = 3; i <= max; i+= 2) {
        if (!not_prime[(i - 1) >> 1])
            total += i;
    }
    std::cout << total << std::endl;
    return 0;
}

File: pi1000000.gif (4KB, 654x452px) Image search: [Google]

4KB, 654x452px

>>59535799
>But what if I ask you to calculate it?
If you want a calculation rather than the number I would give you the product of a curve. Pi(x).

If you actually needed the real number I have that. If not here's a fast scalable approximation that is surely good enough for whatever use you have for the sum of the first 2 million primes.

I can't even guess why you would need to calculate that, maybe if you were sending a space probe into an area of suggested questionable physics and you can check to see if math changes as the probe enters the zone?

>>59535465
>>59535436
Note that in the original code I allocated too much memory, it should have been:

    std::vector<bool> not_prime((max >> 1) + 1);

(divided by 2, not multiplied by 2)

Fixed in the final version here >>59535893

>>59535893
I wonder if there's a way to optimise this so that you only need to increment i by one and don't need to shift the index in the first loop.

File: prime-count-vector-int.png (75KB, 512x362px) Image search: [Google]

75KB, 512x362px

>>59535698
>>59535617
>>59535520
(platform: MacBook Pro Retina 15" Early 2013, 2.4 GHz Intel Core i7, 8GB RAM)

run time of vector<bool> for 2 million integers: 3,512 us

run time of vector<int> for 2 million integers: 7,136 us

run time of vector<bool> for 2 billion integers: 8,970 ms

run time of vector<int> for 2 million integers: 41,273 ms

memory usage of vector<bool> for 2 billion integers: 119.7mb
memory usage of vector<int> for 2 billion integers: 3.73 gb

So in summary, using vector<int> instead of vector<bool> means using 32 times the memory, for a 4.6x slow down.

I know I'm beating a dead horse but how does it feel like to be blown the fuck out of the planet?

/g/ might like this problem

Let S be a sequence with the first term being 1 and the last term being 20!
Let k be the number of terms in S

Find the minimum value of k provided that every term in S has to be able to be written as a sum, difference, or product of two previous terms; this rule excludes the first term, but includes the last term; using a single previous element twice is allowed (ie the term after 1 can be 1+1).

I found a solution for k=27 which I'll post if anyone else finds a solution

File: sieve.png (14KB, 384x476px) Image search: [Google]

14KB, 384x476px

Thoughts? its pretty quick and small, memory wise.

>>59536191
Your problem is not well formed, try again

>>59536226
You might have a better time if you use a separate retrieve and set bit functions

>>59536351
What isn't clear?

>>59535606
https://www.youtube.com/watch?v=z43bmaMwagI

>>59536518
>if considered harmful
Wow coding really has gotten cucked.

>>59536962
I replied to my (You) out of genuine kindness. Now watch the fucking video.

File: haskell-fatass.png (142KB, 700x514px) Image search: [Google]

142KB, 700x514px

>>59537068
>Use Haskell
I stopped watching here.

Computers are finite state machines, it's time to accept that.

Ifs, gotos, longjmps are here to stay

t0 = performance.now();
function sumPrimes(num) {
  var prime, sum = 0;
  for (var i = 2; i <= num; i++) {
    prime = true;
    for (var j = 2; j*j <= i; j++) {
      if (i%j === 0) {
        prime = false;
        break;
      }
    }
    if (prime) sum += i;
  }
  return sum;
}
sumPrimes(2000000);
t1 = performance.now();
t1 - t0;

Sieve in Python, still pretty slow, because Python (~0.33s):

MAX = 2000000
HALF = MAX//2
v = [0]*HALF
total = 2
for i in range(1, HALF):
    if not v[i]:
        n = 2*i + 1
        total += n
        for j in range(i, HALF, n):
            v[j] = 1
print(total)

>>59522949
not for embedded microprocessors you shit

>>59517556
You've got to be trolling me.

while p**2 < limit:

>>59517440
What is this, and how does it work? Forgive me as I am a noob

File: 1410850624644.jpg (108KB, 806x610px) Image search: [Google]

108KB, 806x610px

>>59537790
How do you get the upper range of primes > HALF from this? I don't understand the maths logic behind this

>>59538233
We only need to check odds (of which there are MAX//2), so v is a list of HALF elements such as v[i] corresponds to the number 2*i+1.

import wolframalpha
client = wolframalpha.Client(app_id)

res = client.query('Find the sum of all primes below two million')
print(next(res.results).text)

>>59518747
> What's wrong with this, actually?
Since you know the stopping condition before entering the loop you should use it as the loop condition.
This may not make much of a different from a python point of view may yield great optimizations in C/C++ since the compiler can unroll and vectorize

File: sieve.jpg (24KB, 517x262px) Image search: [Google]

24KB, 517x262px

>>59537790

>>59516680
ez pz

int I = 0
int ret = 0
while I < 2000000
    if I is prime:
        ret += I
    I += 1
return ret

>>59539099
>143042032116
Yeah, no.

File: sieve.png (23KB, 522x244px) Image search: [Google]

23KB, 522x244px

>>59539228
fixed

File: CaOW0M9XEAAQsdC[1].jpg (27KB, 557x605px) Image search: [Google]

27KB, 557x605px

>>59539434
>console.log(sum)

>>59524556
>rust

>>59535477
That's not a bitmap, you're talking about an array of bitfields.

>>59535388
In C, you can make use of all 8 individual bits of a byte via bitfields or via bitwise arithmetic.
something like arr[j] &= (1 << i % 8) would set individual bits as needed

>>59534742
This, it's the most basic optimization, it can reduce the number of iterations dramatically

>>59532031
>>>notUsingCamelCase
>>59531796
>not Using Camel Case

>not_Using_Snake_Camel_Case

In Haskell this is just

include Monad.Primes.Monad;
let Primes.Sum(0,2000000);
do;

>>59523971
Come on it's fucking prime numbers not some imaging library. There is a difference between prime numbers and some huge framework.

there is no efficient way to do it. primes don't have a known pattern.
even if you sum them in series rather than generate than sum, it doesn't matter. it's the same number of operations.

in 2 days op will be back asking for bubble_sort function

>>>/hw/

>>59545031
>there is no efficient way to do it
But there is, brute force vs sieve, arrayed sieve vs memory efficient sieve, and just optimization of algorithms in general. Even just knowing basic properties of primes, like them being odd, will allow code to be efficient, like the difference between

if i%3 == 0 and i%5 == 0

vs

if i%15 == 0

in fizzbuzz.

>>59545211
sepples already has a sort()

I'm a mathematician, not a (professional) programmer, but here's what I'd do

primes = []
n = 2
while n <= 2e6:
    bound = n ** 0.5
    is_composite = False
    for p in primes:
        if p > bound:
            break
        if n % p == 0:
            is_composite = True
            break
    if not is_composite:
        primes.append(n)
    n += 1
print(sum(primes))

>>59546367
what gay shit is this

cobol?

>>59545401
algorithms for generating primes sure, but not for summing them like you would for a geometric series.

>>59546367
awful

>>59546403
its python..

File: 1400034716231.png (134KB, 334x393px) Image search: [Google]

134KB, 334x393px

>>59546367
>increments in 1 instead of 2
>doesn't start from n = 3, primes = [2]
>I'm a mathematician

lim<n : +2000000>Σ<i = 1>prime(n)

If you're all going to do it in quadratic time with a separate prime testing function, you may as well

print(sum(filter(lambda n: all(n % i for i in range(2, n)), range(2, int(2e1)))))

>>59546723
yeah, but in Haskell this is just

include Monad.Lambda.Monad;
include Monad.Primes.Monad;
let do Lambda.Primes;

>>59546723
summing isn't quadratic and neither is finding primes.

>>59546759
yeah but doing them both at the same time is

>>59546723
>you may as well
This is far slower than any trail division method like >>59519381
Just terrible, like most one liners.

>>59545031
>there is no efficient way to do it
Efficiency is not a binary thing. There are more or less time-efficient ways to do this, and more or less memory-efficient ways to do this.

>primes don't have a known pattern.
All primes above 3 are in the form of 6*k±1, which some trial division approach algorithms take advantage of (see >>59518527).

Seive is probably the best way but since no-one seems to have posted one, here's a Miller-Rabin implementation. Finds the correct answer in ~0.2s on my 3770K. You can look up more bases for witness if you need them.

#include <iostream>
#include <cmath>

size_t power(size_t a, size_t n, size_t mod)
{
    size_t power = a;
    size_t result = 1;
    while (n)
    {
        if (n & 1)
            result = (result * power) % mod;
        power = (power * power) % mod;
        n >>= 1;
    }
    return result;
}

bool witness(size_t n, size_t s, size_t d, size_t a)
{
    size_t x = power(a, d, n);
    size_t y;

    while (s) {
        y = (x * x) % n;
        if (y == 1 && x != 1 && x != n-1)
            return false;
        x = y;
        --s;
    }
    if (y != 1)
        return false;
    return true;
}

bool is_prime_mr(size_t n)
{
    if (((!(n & 1)) && n != 2 ) || (n < 2) || (n % 3 == 0 && n != 3))
        return false;
    if (n <= 3)
        return true;    
    size_t d = n / 2;
    size_t s = 1;
    while (!(d & 1)) {
        d /= 2;
        ++s;
    }
    
    if (n < 9080191)
        return witness(n, s, d, 31) && witness(n, s, d, 73);
    if (n < 4759123141)
        return witness(n, s, d, 2) && witness(n, s, d, 7) && witness(n, s, d, 61); 
    return witness(n, s, d, 2) && witness(n, s, d, 325) && witness(n, s, d, 9375) && witness(n, s, d, 28178) && witness(n, s, d, 450775) && witness(n, s, d, 9780504) && witness(n, s, d, 1795265022);
}

long counttoprimes(long limit){
    long accumul = 5;
    int step = 4;
    for (size_t i=5; i<limit; step=6-step, i+=step) {
        if (is_prime_mr(i)) {
            accumul+=i;
        }
    }
    return accumul;
}

int main(int argc, char* argv[])
{
    long z = std::stol(argv[1]);
    std::cout << z << '\n' << counttoprimes(z) << '\n';
} 

>>59547621
>since no-one seems to have posted one
Multiple sieves have been posted. The third post is a sieve.

>>59547649
I meant that no-one seems to have posted a Miller-Rabin implementation.

>>59516680
Not very efficient, but not the worst. I haven't written C in a while and I don't feel like looking up existing efficient algorithms (I think the point was to do it yourself).

#include <stdlib.h>
#include <stdio.h>

int isprime (int *parray, int num, int length)
{
  int status = 1;
  
  for (int i = 0; i < length && (parray[i] < (num/2)); i ++)
    {
      if (! (num % parray[i]))
    {
      status = 0;
      break;
    }
    }
  
  return status;
}


int main (int argc, char *argv[])
{
  if (argc < 2)
    exit(EXIT_FAILURE);

  int total = atoi(argv[1]);
  int length = 0;
  long sum = 0;

  printf("Primes 2 - %i (non-inclusive of upper bound)\n", total);
  
  int *parray = malloc(((total / 2) + 1) * sizeof(int)); //maximum possible primes for any given size range
  parray[0] = 3;

  for (int i = 3; i < total; i += 2)
    {
      if (isprime(parray, i, length))
    {
      parray[length] = i;
      length ++;
      sum += i;
    }
    }

  if (total >= 2)
    sum += 2;

  printf("Sum: %ld\n", sum);

  free(parray);
  exit(EXIT_SUCCESS);
}

Output running on AMD Phenom 2 1100T (3.3GHz):

Primes 2 - 2000000 (non-inclusive of upper bound)
Sum: 142913828922

real    1m17.513s
user    1m17.444s
sys    0m0.036s

>>59535465
smax should be sqrtmax, total shouldn't be a const and endl not decalred in scope, should be std::endl, cstint is superflouous. Other than that, pretty quick, nicely done.

>>59547703
My bad. But do you need a maths background to implement this? I can implement a sieve and understand the gist of it, but the Miller-Rabin wiki page is all jargon to me

>>59547910
Oh also it gives the wrong answer, 142913828818 instead of 142913828922, so there's that.

>>59547961
It probably helps. It is considerably tougher to understand than a sieve.

>>59518838
>implying 2*1511 is a prime
your logic is flawed
>total uninitialized
>if (i==1) total += 1;
you mean if (fag[i] == 1) total += 1; but that's still pretty bad choice. you should mean total += fag[i];
>nested for loops
>not even for(int j = i; ...
>2MB array in the stack

>>59538103
Shell (probably POSIX); it calls a program called "primes" located in the /usr/games/ directory, with arguments 2 and 2000000, then pipes the output of that into sed to sum it.

So basically this depends on "primes" returning a list of primes, i.e. it doesn't actually do any work itself.

What is this "putting your data structure on the heap" meme

Rate my sieve of mesothelioma!

#define LIMIT 200000000
#define BITS (sizeof(char) * CHAR_BIT)

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

File: okeLUiZ.png (16KB, 392x316px) Image search: [Google]

16KB, 392x316px

Made it more complicated than it needed to be

142913828922

>>59549244
>lis
>for each
>x+=1
please no

>>59549090
that is NOT an acceptable use of the ternary operator!

>not doing this through dynamic programming
wowzers

>>59549401
>not doing this in jewish mysticism

>>59548094
>>59547910

The final version of the code is here >>59535893

Both problems are fixed.

It gives the correct solution (142,913,828,922)

>>59516680
So is the answer 142980410988?

>>59547703
>Miller-Rabin implementation
Miller-Rabin would end up being slower.

>>59549401
See:

limit = 2000000
primes = list()

primes.append(2)
for i in range(3, limit):
    for j in range(len(primes)):
        if (i % primes[j] == 0):
            break
    else:
        primes.append(i)

print(sum(primes))

>>59549401
>dynamic programming
slower than sieve.

>>59535893
Found a very subtle bug

#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

int main() {
    const int max = 2000000;
    const int smax = std::sqrt(max);
    std::vector<bool> not_prime((max >> 1) + 1);
    not_prime[0] = true;
    for (int i = 3; i <= smax; i+= 2 ) {
        if (not_prime[(i - 1) >> 1])
            continue;
        for (int j = i * i; j <= max; j+= (i << 1)) {
            not_prime[(j -1) >> 1] = true;
        }
    }
    int64_t total = 2;
    for (int i = 3; i <= max; i+= 2) {
        if (!not_prime[(i - 1) >> 1])
            total += i;
    }
    std::cout << total << std::endl;
    return 0;
}

See if you can find the required change (don't cheat and use diff)

Interestingly, in MSVC on an i5 3750K, it took 9.786s, whereas it took a lot less time (8.97s) on the mobile i7. Microsoft's compiler sucks.

>>59549636
wait, why?
wouldn't PD make less comparisons?

absolutely ancient thing i wrote pt. 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define nmsize (sizeof(num)/sizeof(num[0]))
#define bitsize (nmsize*8)
#define kpsize (sizeof(kp)/sizeof(kp[0]))
#define whlsize (sizeof(wheel)/sizeof(wheel[0]))

unsigned char num[1000];
unsigned char bits[] =
{
    1, 2, 4, 8, 16, 32, 64, 128,
};
int kp[] =
{
      2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
     31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
     73, 79, 83, 89, 97,101,103,107,109,113,
    127,131,137,139,149,151,157,163,167,173,
    179,181,191,193,197,199,211,223,227,229,
};
int wheel[] =
{
    10, 2, 4, 2, 4, 6, 2, 6, 4, 2,
     4, 6, 6, 2, 6, 4, 2, 6, 4, 6,
     8, 4, 2, 4, 2, 4, 8, 6, 4, 6,
     2, 4, 6, 2, 6, 6, 4, 2, 4, 6,
     2, 6, 4, 2, 4, 2,10, 2,
};

void zap(double n, long i)
{
    int j;
    double temp;
    
    modf(n/i, &temp);
    j = i*temp - n;
    if(j < 0)
        j += i;
    for(; j <= bitsize; j += i)
        num[j>>3] |= bits[j&07];
}

>>59549894

void main(int argc, char *argp[])
{
    double n, temp, end, v;
    long long sum;
    
    n = atof(argp[1]);
    end = atof(argp[2]);
    
    if(n==0)
        n=1;
    if(n<230) {
        for(int i=0; i<kpsize; i++) {
            if(kp[i]<n)
                continue;
            if(kp[i]>end) {
                printf("%lld\n", sum);
                return;
            }
            sum += kp[i];
        }
        n = 230;
    }
    
    modf(n/2, &temp);
    n = 2.*temp+1;
    
    for(;;) {
        /* clear */
        for(int i = 0; i < nmsize; num[i++] = 0);
        /* sieve */
        v = sqrt(n+bitsize);
        zap(n, 3);
        zap(n, 5);
        zap(n, 7);
        for(int k=11, i=0; k<=v; k+=wheel[i]) {
            zap(n, k);
            i++;
            if(i >= whlsize)
                i = 0;
        }
        /* print */
        for(int i=0; i<bitsize; i+=2) {
            if(num[i>>3] & bits[i&07])
                continue;
            temp = i + n;
            if(temp > end) {
                printf("%lld\n", sum);
                return;
            }
            sum += temp;
             }
             n += bitsize;
         }
}

Noob here. rate?

#include <iostream>

using namespace std;

int main() {
  long long int a=0;
  int n;
  int t=1;
  int pt[2000000] = {1};
    for (n=2; n<=2000000; n++) {
      bool b=true;
      int k=1;
      while (pt[k]*pt[k]<=n && pt[k] >= 1) {
        b = b && (n % pt[k] != 0);
    k++;
      }
      if (b) {
    a += n;
    pt[t]=n;
    t++;
      }
    }
    cout << a << endl;
    cin.get();
    return 0;
}        
           

>>59549842
Sieve doesn't need any comparisons, no divisions or looped multiplications.

Sieve is O((n log (n) log log (n)) whereas DP would take O(n^2/log(n)), but even the run time is faster since no divisions are made.

The only trade-off is memory usage but even then, the Sieve is O(n) whereas DP would be O(n/log(n)) (marginally better).

Deterministic Miller-Rabin can be done in O(n log(n)), with constant memory usage up to n=2^64, but the operations are so heavy the runtime will be a lot worse.

>>59549954
Oh damn I think I should brush up on my algorithms and complexity analysis then
thanks!

long long n

n long n

n n long n

n^2^2 n long n

long n^2 long n long long long n

For really big numbers, doing the actual sums is not feasible, and we transcend from fizzbuzz into number theory:

1) Estimate upper nth prime for a given sum = (n^2)/2 * ln(n)
2) Estimate the nth prime value, x = n log n

You run this algorithm partitioning n long enough until you get closest sum. Alternatively, you can invert the 1) formula with use of Lambert-W function, but I think it asymptotically boils down to the same (divide and conquer).

>>59550179
Found a more formal description:

http://mathoverflow.net/questions/63412/upper-bounds-for-the-sum-of-primes-up-to-n

Obviously the result is only estimate, getting the actual value will be close to impossible for large sums.

>>59548232
I tried to implement the Wikipedia pseudocode literally in Python, and failed:

from random import randint

def is_prime(n, k=10):
    if n == 2 or n == 3:
        return True
    if not n & 1:  # Check if even, faster than modulo
        return False
    r = 0
    d = n - 1
    while d % 2 == 0:
        d //= 2
        r += 1
    for i in range(k):
        CONT = False
        a = randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == (n - 1):
            CONT = True
        for i in range(r - 1):
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == (n - 1):
                CONT = True
        if CONT:
            continue
        else:
            return False
    return True

SUM = 0
for i in range(2, 2000000):
    if is_prime(i):
        SUM += i
print(SUM)

>>59517030
What shitty language is this?

>>59516680
This is a great interview question. Adding it to my list.

Thanks!

>>59551369
I detest you already.
You're expressing the mind of a 5 year old if you think this is a great question or if you can't think of something more interesting and insightful with 1 minute of your time. The fact that you claim to have a list of babby questions is pathetic.
Your communication/interaction manner is all wrong for 4chan:
Your statement is almost objectively wrong so you're not even highlighting something of value, for the benefit of other anonymous users.
Anonymous users aren't seeking praise, especially when they're clearly offering a challenge, but you're not praising the person who posted 18 hours ago. They probably aren't here so your valueless "thanks" is pointless, potentially conducive to more of the stupidity which you express, and, essentially, disingenuous due to:
Under the (fair) assertion that your statement has productive value to others, it's clearly an act self-satisfaction.
4chan isn't your tumblr nor facebook nor does it offer you a user reputation - not that anyone in reality gives a fuck about how many likes you have for pretending to be a deluded, valueless bastardization of "nice" - no one is offering you virtual praise. No one cares to imagine your situation - so mentioning it when it provides nothing to the reader is, as mentioned, self-serving blogging.
I admit that I may have a tiny bias based on vague recalling your trip as being obnoxious, from a distance past.
I am pretty tired, too.
By the way if anyone would like to provide some critique of my blithering it would be really helpful and appreciated for exploring how to explain, to shitlords, how to make use of the internet and other communication and collaboration.

File: Untitled2.png (196KB, 1282x1055px) Image search: [Google]

196KB, 1282x1055px

>>59551626
I do not detest you.

FYI: /g/ frequently has "interview and CV/resume threads", and this is usually programming/IT oriented. I like these threads, and often find some gems in them. I have taken some of the best questions from such threads, and use them in a list when I do interviews.

You believe that this is a bad interview question. That is fine. If you do not like it, do not use it in your interviews.

You are right: This is not tumblr, or facebook, or twitter. I cannot harvest "likes" or "mentions" or "retweets". Since I cannot benefit, why are you angry with me? Why does it upset you, that I say "Thanks!" to OP? OP may or may not be here, but how does that affect my gratitude?

If you are upset that I did not contribute much to the thread, then:

1- Your long whine does not contribute either.
2- I can fix it by posting the questions I use in interviews. Pic related, and you can see OP's question has been added.

Hope you have a pleasant day ahead, and that whatever is irking you irl gets fixed.

>>59551626
somebody is taking 4chan way too seriously.

>>59551787
It's just an open forum with people willing to share genuine and both frank and thoughtful ideas. A good place to practice argument.

>>59551787
no such thing as too seriously

>>59549488
It still appears to be faster than trial division, at least in Python

>>59551751
I'm glad to see a reasoning response. Some memory which I have of your trip being annoying does not resonate with the demanour that I'm seeing.

>>59551751
What's the 12x12 table?

File: Untitled.jpg (158KB, 747x557px) Image search: [Google]

158KB, 747x557px

>>59553003

>>59551369
You do realise that writing a viable function checking a number for primality correctly without using google is a "How fresh you're out of college" question, right?
Unless the job specifically requires that kind of knowledge, is there a use for such question?

>>59553155
Some people want to hire programmers, not copy/pasters. Look up the origins of FizzBuzz, and you will find that 99.5% of all programming-job applicants cannot program at all.

And if you think OP's question is easy, check the first set of questions I have here: >>59551751

>>59553169
I don't think OP's question is easy, I think it is complicated to do right without reference. And interviews being interviews you may be called out for using a library function or trying to google for nonretarded algorithm to check primality.

>>59553191
>without reference
Reference for checking primality? Or for summation?

>>59553203
Reference for checking primality not by trial division.

>>59553227
How will this help the interviewer learn about the candidate's ability to think on their feet?

>>59553253
So, you don't care about time spent in this question? Doesn't matter if solution will be impractical?

>>59553317
>So, you don't care
I care mate, I care a lot.

>>59537961
>taking a power every loop
Incredibly inefficient

>>59553360
That means you want me to reinvent the wheel. We're not in Ancient Greece anymore but take a look over here:
https://web.archive.org/web/20160619103848/http://www.nomachetejuggling.com/2014/06/24/the-worst-programming-interview-question/

>>59516834
>holy fuck did /g/ make me learn something?

Just implemented a generic Eratostenes function in C.
* Takes an input max.
* Returns a properly sized array of the primes up to max along with the array size. Or NULL and 0 if there's a memory allocation failure.

I'm not posting it though because /g/ will shit on it for my coding style. (Comments; white space; camelCase). If I'm ever asked in an interview now, I'll remember this one.

Odd note: malloc was failing when I tested 2,000,000 max. It wouldn't return NULL but it resulted in an access error midway through the array. (Yes, I multiplied by sizeof(int).)

But calloc works fine.

Is there a limit on malloc that I'm not aware of??? 2mil * int is only 7.6MB so why the fuck would that fail?

>>59553253
>How will this help the interviewer learn about the candidate's ability to think on their feet?
For those who don't understand, an interviewer will give the interviewee hints that will lead them to the correct solution.

>>59516680

#include <stdio.h>

#define MAX 2000000

void sieve(int arr[])
{
    for (int i = 0; i < MAX; i++) {
        arr[i] = i + 1;
    }
    arr[0] = 0;
    int j = 0;
    for (int i = 1; i < MAX; i++) {
        j = 2 * i + 1;
        while (j < MAX) {
            arr[j] = 0;
            j += i + 1;
        }
    }
}

void printarr(int arr[])
{
    for (int i = 0; i < MAX; i++) {
        if (arr[i] != 0) printf("%3d\n", arr[i]);
    }
}

int main()
{
    int arr[MAX] = { 0 };
    long sum = 0;
    sieve(arr);
    printarr(arr);
    for (int i = 0; i < MAX; i++) {
        sum += arr[i];
    }
    printf("\nSum of primes until %d: %ld\n", MAX, sum);
    return 0;
}

Thanks /g/, that was quite fun for a change

Sum of primes until 2000000: 142913828922

>>59553453
>knowing what a prime is
>reinvent the wheel
How about you finish high school math before applying?

>>59553169
>Some people want to hire programmers, not copy/pasters.

But are rarely written math algorithms a true test of programming skill?

The fact that there are multiple approaches to primality tests...including algorithms which trade off between accuracy and speed...mean that the "correct" answer is only going to come from a fresh college graduate who has memorized what others have done, or a veteran who knows how to Google what others have done.

A better test would be a question with all the necessary information in the question. Something that would distinguish between lazy programmers and programmers who can write clean yet speed/memory optimal code. But not something that has been debated and published by PhD's.

>>59553539
>knowing what a prime is
>same as knowing the optimal algorithm for testing primes

How about you finish high school logic before interviewing people?

>>59516680

import requests
import re
sp = requests.get('http://www.mathblog.dk/sum-of-all-primes-below-2000000-problem-10/')
answer = re.search('Prime sum of all primes below 2000000 is \d',sp)
print(answer)

>>59553453
>That means you want me to reinvent the wheel.
As a matter of fact, yes, I do. In an interview, people WILL ask questions to which a solution already exists. It is not to waste time; I know that a solution exists... I want to know if YOU can solve it.

>>59553566
This thread is about a FizzBuzz alternative.

This is not a case where we have 8 different candidates who are all perfectly proficient programmers on the same level as Carmack, and we want to find the candidate who is 165 IQ, as opposed to the other 7 with "only" 160 IQ. We are simply try to check whether the programmer is able to solve a simple problem, or not.

>>59553582
>same as knowing the optimal algorithm for testing primes
Where does it say you have to know it? If you don't, just implement trial division, while noting the limitations of such method. But if you go straight to searching for algorithms you don't understand, you're a fool, and it'll show.

>>59553619
Then I'll probably wont pass your interview with my current knowledge because trial division with passing on even numbers is the only thing I can think of. I spent 4 academical hours on primal numbers and never heard of them again after that except for news about bug in cryptosoftware.

>>59553675
You might pass the technical part, but you will not go far with that attitude. It is not just your supervisor that will be evaluating you, but also HR. HR does not like hiring depressed defeatists.

>>59553643
Yet you missed the point that primality is not a simple problem. Eratostenes is easy to remember, but just as easy to not discover under interview pressure, only to Google at home and go "DOH OF COURSE!"

File: 1450002214528.png (444KB, 800x600px) Image search: [Google]

444KB, 800x600px

>>59518717
>boolEAN

>>59553671
>we don't want someone who can copy/paste
>ask interview question best answered by online research followed by copy/paste

Honestly, I would assume trial division would lose the job and be struggling to think of a more efficient solution (if I didn't remember one off hand).

>>59553705
That can be easily solved

If you are stuck then the interviewer would quickly sketch the Eratoshenes sieve on the whiteboard and you would implement it

>>59553705
>just as easy to not discover under interview pressure
Good thing that the interviewer will have a set of questions ready, and not just one.

>>59553694

Interview World: "You need to answer this academic question which means remembering shit from college that you'll never use in this job OR being an IQ165 genius who will leave our company the moment the NSA offers 3x what we pay."

Real World: "We need a fast primality check under these conditions. What? No, don't fucking waste time trying to figure it out yourself! I want to leave on time so we can hit the strip club. Google to see what existing solutions are available and adapt the best one for our needs."

I understand that nobody wants a copy/paste pajeet, but a good developer recognizes when he should survey published solutions and opinions rather than waste time pretending to be a PhD with tenure.

Don't ask questions where the truly best answers are "honestly, academics spent years on this one so we should probably fucking Google it."

>>59516680

#include <stdio.h>
#include <string.h>

#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;

long long sumPrimes(int n) {
    int m = (n-1) / 2;
    char b[m/8+1];
    int i = 0;
    int p = 3;
    long long s = 2;
    int j;

    memset(b, 255, sizeof(b));

    while (p*p < n) {
        if (ISBITSET(b,i)) {
            s += p;
            j = (p*p - 3) / 2;
            while (j < m) {
                CLEARBIT(b, j);
                j += p;
            }
        }
        i += 1;
        p += 2;
    }

    while (i < m) {
        if (ISBITSET(b,i)) {
            s += p;
        }
        i += 1;
        p += 2;
    }

    return s;
}

int main(void) {
    printf("%lld\n", sumPrimes(2000000));

    return 0;
}

>>59553724
If an interviewer did that, then it's an OK question. An English description of the steps should be enough to write the algorithm.

>>59553694
>not lying about your skills
>that attitude
Well, since I have no need to look for another job, I also have no need to lie on my resume or during interview about my 1337 skills.
If the opportunity ever comes or there will be a need for myself to create one, I'll have to read a few books to become a real programmer.

>>59553764
>sum of primes below 2 million
>honestly, academics spent years on this one so we should probably Google it
Amazing.

>>59516680

def isPrime(input):
    from math import sqrt
    if input in (0,1) or num!=2 and input%2==0:
        return False
    for i in xrange(3, int(sqrt(input)), 2):
        if input%i==0:
            return False
    return True

def sumOfPrimes(n):
    sum = 0
    for i in xrange(n):
        if isPrime(i):
            sum += i
    return sum

print sumOfPrimes(2000000)

>>59553765
autism

>>59553132
I thought It'd have been somthing different.

How is this not the first question?

>>59553793
I bet you cannot remember the various algorithms and their time/space/accuracy trade offs. Much less who came up with them and when.

It would be fun to interview you actually. No Google...and watch that attitude!

>>59551751
How is angle between minute and hour hand in 2:20 hard mode? Seemed easier than the first one for me.

>>59553566
>But are rarely written math algorithms a true test of programming skill?

They're a test of:
- whether you're able to approach a problem at all without googling the solution
- how you approach it
- how you find an explain the solution
- how you translate it into readable code
- whether you can take hints and suggestions from the interviewer.

It's not about being able to provide optimal solution from the top of your head. It's not even about the solution itself. It's about how you think.

>>59516680
>accumulator

What's that

def sumOfPrimes(n):
    sum = 0
    product = 1
    for i in xrange(n):
        v = product/i
        if v == int(v):
            sv = sqrt(v)
            if sv!= int(sv):
                sum = sum+i
                product = product*v
    return sum

use your brain, plebs

>>59553940
I say as I throw in v on the last line instead of i

never go full retard, kids

>>59553940
ZeroDivisionError

>>59553891
Whether or not those points are true depends on the question chosen, how it's phrased, and the suggestions provided.

>>59553961
shit like this is why I'm unemployed.

the theory is sound tho

>>59553891
Do you like XOR swap?

>>59535893
You can also skip the check if the last digit is 5.

>>59516680

Literally a one liner in Ruby..

require 'prime'

Prime.each(2_000_000).reduce {|acc, nr| nr}

>>59554103
Sorry, anon, you must implement your own slow, inefficient, bug-ridden function that will count pseudoprimals to pass.

Easiest I could think of, should be done in C though instead of Java.

public class milprime{

    public static void main (String[] args){
        long total=0;
        boolean [] one_mil = new boolean[1000000];
        for(int i=1;i<1000000;i+=2){
            if(i%3==0)one_mil[i]=true;
            else if(i%4==0)one_mil[i]=true;
            else if(i%5==0)one_mil[i]=true;
            else if(i%6==0)one_mil[i]=true;
            else if(i%7==0)one_mil[i]=true;
            else if(i%8==0)one_mil[i]=true;
            else if(i%9==0)one_mil[i]=true;
        }
        for(int i=1;i<1000000;i+=2){
            if(!one_mil[i]) total+=i;
        }
        System.out.println(total);
    }
}

>>59554167

But why?
Finding primes is super fast with this library.

Also everybody includes something. Is an "Math.sqrt()" import allowed? Is a "#include <stdio.h>" allowed? Where do you draw the line?

>hurr, you code has to be 20 lines
>even though that's not how in works in reality
>even though your solution is perfectly fine in production code

>>59554184
The problem was to find the sum of all primes below two millon, not one, you get an F

>>59554167

OK, so be it.

Here's my "slow, inefficient, bug-ridden function"..

class Fixnum
  def prime_filter 
    (2..Math.sqrt(self)).each {|i| return 0 if self%i == 0}
    self
  end
end

puts (1..2_000_000).reduce {|acc, nr| acc += nr.prime_filter}

(define* (fill-stride! array stride #:optional (start 0))
  (if (< start (car (array-dimensions array)))
    (begin (array-set! array #f start)
           (fill-stride! array stride (+ start stride)))))

(define* (array-find array obj #:optional (start 0))
  (cond
    ((>= (+ start 1) (car (array-dimensions array))) #f)
    ((equal? (array-ref array start) obj) start)
    (else (array-find array obj (+ start 1)))))

(define* (fold-primes proc
                      limit
                      #:optional
                      (start (if (< limit 2) #f 2))
                      (array (make-array #t (+ limit 1)))
                      (accum 0))
  (if (not start)
    accum
    (begin (fill-stride! array start start)
           (fold-primes proc
                        limit
                        (array-find array #t start)
                        array
                        (proc start accum)))))

(display (fold-primes + 2000000))

>>59554217
>But why?
>>59553619
>As a matter of fact, yes, I do. In an interview, people WILL ask questions to which a solution already exists. It is not to waste time; I know that a solution exists... I want to know if YOU can solve it.

>>59554331

You're too late, already done it:
>>59554319

>>59554342

>"Great anon, you're hired!"
>"Sorry, but I dont' want to work here.."
>"What?"
>"A place where people enforce stupid solutions when I already gave an elegant solution which also showed knowledge of the standard libraries is likely to put authority before creativity. Not a place for me. Bye."

>>59536518
>stop using if
*rolls eyes*