How do I sum the primes under two million in C?

>>59746135
it would be faster in javascript

>>59746135

#include <stdio.h>

#define LIMIT 2000000

char sieve[LIMIT] = { 0 };
unsigned long long primes[200000];
unsigned long long count = 0;

void get_primes()
{
    unsigned long long i, j;

    for(i = 2; i < LIMIT; ++i)
    {
      if(!sieve[i])
      {
        primes[count++] = i;

        for(j = i*i; j < LIMIT; j += i)
        {
          sieve[j] = 1;
        }
      }
    }
}

int main(){
  unsigned long long sum = 0;
  unsigned long long i;

  get_primes();
  for(i = 0; i < count; ++i)
  {
    sum += primes[i];
  }

  printf("sum: %lld\n", sum);
}

>>59746150
C doesn't even JIT, of course JS is faster

>sum([x for x in range(2000001) if isprime(x)])

>>59746171
Nice bait

File: fp_not_zero.png (1MB, 904x680px) Image search: [Google]

1MB, 904x680px

>>59746176
kek

>>59746135
Sieve of Eratosthenes.
This thread every fucking day

>>59746135

either way you're getting something in the O(n^2) realm

>>59746153
>not counting out evens immediately
Why?

>>59746135
do your own homework retard

Two million is divisible by two million and therefore not a prime. So the answer is zero.

>>59746673

>not counting out thirdens immediately

why?

>>59747371
because 3's a prime hurr durr

File: question.png (4KB, 176x128px) Image search: [Google]

4KB, 176x128px

check every number (less than 2 million) modulo itself to the power of every exponent less than 2 million, then if its congruent to that number add the base to a list representing your prime number, then sum the list

>>59747415

so is 2 you dumb mongol

>>59746135
If this is a common question, why don't you fags get the right fucking answer?

I know very little about coding, but I know what questions interviewers will ask me for jobs I interview for.

Is this so fucking hard for you guys?

>>59747491
>3D bait

>>59747509

There are different ways to answer this question

Some are retarded but obvious, others less so

Stupd dum smely pepe

Lol

>>59747415
this guy >>59747491 is right.
2 is a prime and is even. So why should I exclude even numbers? That would make the sum incorrect.

>>59749781
Is divisibility by the integers 1 and 2 a meme?

>>59749781
Divisor of 2 greater than 1 and not itself?

By bruteforcing ofc. Sieves and such are for people who go from where the fence is the lowest:

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

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

        unsigned long sum = 0, max;
        int i, a;

        if (sscanf (argv[1], "%lu", &max) != 1) {
           fprintf(stderr, "error - not an (unsigned long) integer");
        } else {

        printf("Calculating the sum of all positive integer primes up to %lu...\n", max);
        for (i = 2; i <= max; i++) {
                for (a = 3; a <= i; a += 2) {
                        if ((i % a) == 0) {
                                if (a == i) {
                                        if (!((i % 2) == 0)) {
                                                sum = sum + i;
                                                break;
                                                }
                                        } else {
                                                break;
                                        }
                        }
                }
        }
        }

        printf("The sum is: %lu\n\n", (sum+2));
        return 0;
}

Is this the new fizzbuzz thread?

File: 7b7.jpg (48KB, 625x626px) Image search: [Google]

48KB, 625x626px

>>59747509

Is this the new FizzBuzz

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

typedef unsigned char bool;
#define SIZE 2000000

int main(int argc, char **argv){
    long int sum = 2;
    bool primes[SIZE] = {0};

    /* Sieve of Eratosthenes */
    for (int i = 2; i*i < SIZE; i++){
        if (!primes[i]){
            for (int j = i*i; j < SIZE; j += i){ 
                primes[j] = 1;
            }   
        }   
    }   

    for (int i = 3; i < SIZE; i += 2)
        sum += i & (primes[i] - 1); 

    printf ("The sum of all primes below %d is %ld\n", SIZE, sum);
}

File: Jacques_Gamelin_-_Alexandre_et_Diogène.jpg (140KB, 736x582px) Image search: [Google]

140KB, 736x582px

>>59746135

def isPrime(n):
    g = []
    h = range(3, n, 2)

    for i in h:
        for x in h:
            if i%x == 0 and i != x:
                g.append(i)

    m = list(set(g)^set(h))
    print(sum(m)+2)

>tfw more intelligent than all of /g/
Feels good to be superior

>no multithreaded solution
didn't expect anything else of /g/

File: 1462411283916.jpg (27KB, 399x385px) Image search: [Google]

27KB, 399x385px

>>59746176

public class Primes{
    public static void main(String[] args) {
        int max = 2000000;
        
        /*This is an implementation of a prime shortcut sourced from a lecture by Professor Thomas Lewis that I attended on the 6th of March 2012. It is contained in lecture slides 2 page 13 of discrete mathematics. I am not stealing it; I am just using it. */
       double thomasLewisTrick = Math.sqrt(max);
       for (int i = 2; i < thomasLewisTrick; i++) {
           if (isPrime(i))  {
               System.out.println(i);
       }

    }
    public static boolean isPrime(int candidate) {
       boolean isPrime = false;
       /// Returns true if the passed number is prime. This exercise is trivial and left to the reader
       return isPrime;
    }
}

>>59750516
kekrino

>>59750516

I am not stealing it; I am just using it.

Whoa, almost had to report you to the plagiarism police before I read that

>>59746264
go back to \v/ brainlet

>>59746153
>tfw I just spent a couple of hours writing a much uglier solution in C just yesterday
>still messed up somewhere

Good job, anon.

I hate you.

>mfw only one of you is using sqrt
>mfw no mfw

>>59746176
>NameError: name 'isprime' is not defined
Thank you for applying. We will call you back. Next! Mr. Dinesh Satyapooh!

>>59746153
>char sieve[limit]
>char

(1000000*2000000*(log(2000000)))

>>59746135
Is there a C preprocessor directive to get the square root of a constant in compile time?
If so, I got it.

>>59751741
>square root
>prime

nigger what

>>59751749
It's to define the capacity of a helper buffer without malloc, nothing else.

>>59746
>>59746135
For you

>>59751741
Well if you do something like #define number 10/2 what do you expect to get?

Just don't expect it to work very well with floating point numbers.

File: 1462521509205.jpg (37KB, 640x445px) Image search: [Google]

37KB, 640x445px

>>59752232
Anyways, I got it.

#include <stdio.h>

#define PRIMES_UP_TO        2000000
/* floor(Sqrt(PRIMES_UP_TO)) */
#define PRIMES_UP_TO_SQRT   1414

int main(int argc, char** argv)
{
    unsigned long long int sum, sum2;
    unsigned int i, j, mult;
    unsigned int primes[PRIMES_UP_TO + 1] = {0};
    
    primes[2] = 2;
    sum = 2;
    sum2 = 0;
    
    /* Sum all odd numbers */
    for(i = 3; i < PRIMES_UP_TO; i += 2)
    {
        sum += i;
        primes[i] = i;
    }
    
    /* Substracts all non-prime numbers */
    for(i = 3; i <= PRIMES_UP_TO_SQRT; i+=2)
    {
        if(primes[i] == 0)
            continue;
        
        for(j = i; j <= (PRIMES_UP_TO / i); j+= 2)
        {
            mult = i*j;
            if(primes[mult] == 0)
                continue;
            
            primes[mult] = 0;
            sum -= mult;
        }
    }
    
    for(i = 0; i <= PRIMES_UP_TO; i++)
    {
        if(primes[i] != 0)
        {
            printf("%u ", i);
            sum2 += i;
        }
    }
    
    printf("\nResulting sum is: %llu.", sum);
    printf("\nResulting sum2 is: %llu.\n", sum2);
    
    return 0;
}

Is 142913828922 the right result?

>>59752389
No, 142913828921 is.

>>59752389
my sieve and trial division implementations both return 1179908154 as the sum of all primes <2000000. How many primes are you getting?

SIFT THE TWOS

SIFT THE THREES

THE SIEVE OF ERATOSTHENES

WHEN THE MULTIPLES SUBLIME

THE NUMBERS THAT REMAIN ARE PRIME

>>59746135
It's really not very hard, this is a not optimized Java solution:

public class PrimesUnder2000000Sum {
    public static void main(String[] args) {
        boolean[] booleans = new boolean[2000000];
        long sum = 0;

        for (int i = 2; i < booleans.length; i++) {
            if (booleans[i]) {
                continue;
            }

            sum += i;

            for (int x = i; x < booleans.length; x += i) {
                booleans[x] = true;
            }
        }

        System.out.print(sum);
    }
}

>>59747371
You're using 1 as a step (i++) when you could use 2 (i += 2), starting from i = 3 and initializing the sieve with 2.

You cut the running time by half by changing 2 lines.

>>59751202
>implying I would be applying for a Java job
Light kek tho

Is this the birth of an epic new meme???

>>59752416
I got 148933 primes. This sums them all.

#include <stdio.h>

/* Assuming this constant is greater than 2. */
#define PRIMES_UP_TO        2000000

/* floor(Sqrt(PRIMES_UP_TO)) */
#define PRIMES_UP_TO_SQRT   1414

int main(int argc, char** argv)
{
    unsigned long long int sum, sum2;
    unsigned int i, j, mult;
    unsigned int primes[PRIMES_UP_TO + 1] = {0};
    
    FILE* primesf = fopen("primes.txt", "w");
    
    primes[2] = 2;
    sum = 2;
    sum2 = 0;
    k = 0;
    
    /* Sum all odd numbers */
    for(i = 3; i < PRIMES_UP_TO; i += 2)
    {
        sum += i;
        primes[i] = i;
    }
    
    /* Substracts all non-prime numbers */
    
    for(i = 3; i <= PRIMES_UP_TO_SQRT; i+=2)
    {
        if(primes[i] == 0)
            continue;
        
        for(j = i; j <= (PRIMES_UP_TO / i); j+= 2)
        {
            mult = i*j;
            if(primes[mult] == 0)
                continue;
            
            primes[mult] = 0;
            sum -= mult;
        }
    }
    
    for(i = 0; i <= PRIMES_UP_TO; i++)
    {
        if(primes[i] != 0)
        {
            fprintf(primesf, "%u\r\n ", i);
            sum2 += i;
        }
    }
    
    fclose(primesf);
    
    printf("\nResulting sum is: %llu.", sum);
    printf("\nResulting sum2 is: %llu.\n", sum2);
    
    return 0;
}

>>59751340
use uint8_t if you want. whatever. No one would waste more than one byte here.

>>59750397
>this much delusion

Here, someone already did it better than you in your meme language: >>59746176

 public static void main(String[] args) {

    BigInteger sum = new BigInteger("2");
    boolean isPrime = true;
    for (int i=3; i<2000000; i++) {
    double aa = Math.sqrt((double)i);
        for (int j=2; j<=aa; j++){
            if (i % j == 0){ 
                isPrime = false;
                break;
            }
        }
        if(isPrime){
            sum = sum.add(BigInteger.valueOf(i));
        }
        isPrime = true;
    }
    System.out.println("Sum  = "+sum); 
} 

>>59751741
Your compiler will do it for you with sqrt().

File: udcbKrU.png (280KB, 569x613px) Image search: [Google]

280KB, 569x613px

            function isPrime(value) {
                for(var i = 2; i < value; i++) {
                    if(value % i === 0) {
                        return false;
                    }
                }
                return value > 1;
            }

            var sum = 0;

            for (var j = 1; j <= 2000000; j++) {
                if (isPrime(j)){
                    sum += j;
                }
            }

            console.log("Sum of primes upto 2,000,000 is: ", sum);

This took Chrome 8 minutes to process

>>59749138
Besides, a sieve would basically remove the evens in the first step.

>>59752607
>>59752416 here.
I'm retarded, didn't think to consider the possibility that I'm overflowing the integer. Changed my 32bit ints to 64bit and got the same result as you do now.

>>59753003
>this took chrome 8 minutes
>webdevs

Gas em all

>>59746135
Google it retard, its on stack overflow

File: iq tiers.png (416KB, 600x848px) Image search: [Google]

416KB, 600x848px

where does prime sum rank?

>>59746153
>Checking evens
>Going up to limit instead of sqrt(LIMIT)
Never gonna make it

>not bumping this thread
do you hate life?

>>59753963
Creating a hard coded list of primes, doing a range check, and summing them should be in there

>>59753279
baby's first program

>tfw your prime checker misses 0.001% for unknown reasons

>>59746135
Why are all these programs so needlessly complicated?

#include <stdio.h>

bool isPrime(long num){
    for (long i = 2; i * i <= num; i++){
        if (num % i == 0) return false;
    }
    return true;
}

int main()
{
    unsigned long long sum = 2;
    for (long i = 3; i < 2000000; i+=2){
        if (isPrime(i)) sum += i;
    }
    printf("%lli\n",sum);
}

>>59755513
>checking to 2000000 instead of sqrt(2000000)
fuck off cuck

>>59755661
There are primes between sqrt(2000000) and 2000000

File: g.jpg (29KB, 722x384px) Image search: [Google]

29KB, 722x384px

i did it /g/

>>59756976
the absolute madman

I don't understand why this meme has come up so much in the past few days. Did somebody write a blog post about not being able to do it in an interview, and how that's not fair?

Sieve of Atkin is best or what?

>>59752389
>142913828922
yes
>>59752405
no

>>59756895
actually factually incorrect my dude

File: notprime.png (4KB, 273x65px) Image search: [Google]

4KB, 273x65px

>>59755661
>>59757285

>>59757392
fake. there is no prime that exists between sqrt(n) and n for any n in the reals. all numbers between sqrt(n) and n are inherently composite to some factor less than or equal to sqrt(n)

import math

def sieveOfAtkin(limit):
    P = 5
    sieve=[False]*(limit+1)
    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2
            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
    for x in range(5,int(math.sqrt(limit))):
        if sieve[x]:
            for y in range(x**2,limit+1,x**2):
                sieve[y] = False
    for p in range(5,limit):
        if sieve[p] : 
            P = P + p
    print P

sieveOfAtkin(2000000)

142913828922

>>59757439
python2.7
real 0m0.979s
user 0m0.960s
sys 0m0.016s


python3
real 0m3.195s
user 0m3.188s
sys 0m0.004s


no wonder nobody uses it

>>59757438
So you mean between 100 and 10 there are no prime numbers?

>>59757523
yes

>>59757439
>sieve=[False]*(limit+1)
Enjoy your memory error trying to sieve anything above a billion.
>>59757473
Regular sieve takes 0.4s in Python3

>>59757621
I did 2 billion and it used 20gb of ram rofl

>>59757438
>>59757549
You're fucking retarded. There are no pair factors above sqrt(n) that haven't already been found below sqrt(n), which is why you don't waste time checking above. It has nothing to do with primes, and you're in fact completely wrong.

>>59757523
what about 11?

>>59746153
>Time: 0.048s
>>59749860
>Time: Still running
>>59750256
Time: 0.036s
>>59752339
>Chookun without printf: 0.077s

Is it really that hard to follow this pseudocode you fucking idiots

Input: an integer n > 1.

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
A[j] := false.

Output: all i such that A[i] is true.

Am I wrong in thinking you could do this with the most basic implementation of this problem? Is the issue that as an interview question people want to see an incredibly efficient version of it?

I did a shitty one in javascript in like 5 minutes that does 2 million almost instantly... I don't see what the problem is, is this just like fizzbuzz with a higher possibility for efficiency?

>>59757621
i'm probably going to try to rewrite my sieve of eratosthenes code from the other thread to be segmented. it won't help in terms of the long as fuck run time, though.

>>59757680
you seem upset

there are no primes above sqrt(n) in the reals. try again.

>>59746135
Jokes on you /g/, a couple more of these threads and I can probably memorize the code to do it.

>>59757621
>0.4s
I got 0.4s in javascript with nothing but "don't test evens except 2"

Maybe if this is an interview question they should make the number higher than 2 million so that more advanced algorithms actually fucking matter?

>some 1's and 0's
vs
>an army of autists who have the whole Internet at their fingertips
/g/ lost pretty hard

>>59757439
>11,5 secs

awful

unsigned long sumprime(int end){
    int start=1;
    int list[end];
    int i;
    for (i=1;i<=end;i++){
        list[i-1]=i;
    }
    unsigned long sum=0;
    int v=0;
    int a;
    for(i=start;i<end;i++){
        a=list[i];
        if (a>1){
            v=a;
            sum+=a;
            while (1){
               v+=a;
               if (v>end) break;
               list[v-start]=0;
            }
        }
    }
    return sum;
}

>>59752641
Are you upset?
Are you mad?
How does it feel to be such a little loser?
I pity those with such an inability to logically think

>>59758102
I posted it as something to talk about
apparently it's the most modern sieve, somehow..?
https://en.wikipedia.org/wiki/Sieve_of_Atkin

>>59757936
>sqrt(11) = 3.316...
>there are no primes above 3, not even 5 and 7, which are prime
What the fuck are you spewing?

>>59746176
>if isprime(x)
Primality test is slower than sieve. Enjoy not getting the job.

>>59746176

my $sum = 0;
for 1...1_999_999 { $sum += $_ if is-prime($_) };
say $sum;

This actually works in Perl6

>>59749860
pajeet we are paying you 5 cents an hour to work, not advertise your horrible programming skills

>>59758150
any number real x where sqrt(n) < x < n for any number real n is composite with some factor real k where k < sqrt(n)

prime reals existing above any sqrt(n) real is a MYTH