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

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

it would be faster in javascript

#include

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

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

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

Nice bait

kek

Sieve of Eratosthenes.
This thread every fucking day

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

>not counting out evens immediately
Why?

do your own homework retard

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

>not counting out thirdens immediately

why?

because 3's a prime hurr durr

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

so is 2 you dumb mongol

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?

>3D bait

There are different ways to answer this question

Some are retarded but obvious, others less so

Stupd dum smely pepe

Lol

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

Is divisibility by the integers 1 and 2 a meme?

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
#include

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

Is this the new fizzbuzz thread?

...

Is this the new FizzBuzz
#include
#include

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

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 Sup Forums
Feels good to be superior

>no multithreaded solution
didn't expect anything else of Sup Forums

...

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

kekrino

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

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

...

go back to \v/ brainlet

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

Good job, user.

I hate you.

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

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

>char sieve[limit]
>char

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

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

>square root
>prime

nigger what

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

For you

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.

Anyways, I got it.

#include

#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

Is 142913828922 the right result?

No, 142913828921 is.

my sieve and trial division implementations both return 1179908154 as the sum of all primes

SIFT THE TWOS

SIFT THE THREES

THE SIEVE OF ERATOSTHENES

WHEN THE MULTIPLES SUBLIME

THE NUMBERS THAT REMAIN ARE PRIME

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

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.

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

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

I got 148933 primes. This sums them all.
#include

/* 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

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

>this much delusion

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

public static void main(String[] args) {

BigInteger sum = new BigInteger("2");
boolean isPrime = true;
for (int i=3; i

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

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

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

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.

>this took chrome 8 minutes
>webdevs

Gas em all

Google it retard, its on stack overflow

where does prime sum rank?

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

>not bumping this thread
do you hate life?

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

baby's first program

>tfw your prime checker misses 0.001% for unknown reasons

Why are all these programs so needlessly complicated?
#include

bool isPrime(long num){
for (long i = 2; i * i

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

There are primes between sqrt(2000000) and 2000000

i did it Sup Forums

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?

>142913828922
yes
no

actually factually incorrect my dude

...

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

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

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

yes

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

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

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.

what about 11?

>Time: 0.048s
>Time: Still running
Time: 0.036s
>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?

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.

you seem upset

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

Jokes on you Sup Forums, a couple more of these threads and I can probably memorize the code to do it.

>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
Sup Forums lost pretty hard

>11,5 secs

awful

unsigned long sumprime(int end){
int start=1;
int list[end];
int i;
for (i=1;iend) break;
list[v-start]=0;
}
}
}
return sum;
}

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