Asked to sum the primes under two million

>asked to sum the primes under two million

Other urls found in this thread:

en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Computational_analysis
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
twitter.com/SFWRedditImages

> store all integers under 2 million as unsigned long int
> this will only require 8 MB of memory
> start with 2, remove all that are dividable with 2
> remove all that are dividable with 3
> 4 has already been removed, so remove all that are dividable with 5
continue until you reach the end of your list, then you're left with only primes. sum them

this will probably take less than a second if you use c++

picture unrelated

I saw one of these threads earlier and tried to make a C program to solve it. It behaves inconsistently though. I'm not really familiar with C, could you find the problem?
$ ./a.out 2
2 is prime!
The sum of all primes

Nevermind, it's my memset

>this will probably take less than a second if you use c++
to be honest it should take under 1 second in python, and a retard-short time in a compiled language

nice O(n^2)

Atleast memory complexity is 1.

Wasn't trying to optimise it in the slightest, just trying to get something that worked.

Actually its n

Well, optimalization you need also needs rewrite most of that code.

int prime_sum (int n) {
sum=0;
for (i=1;i

you want sum only, why the fuck store all numbers? why you just dont sub from 2M, test that number and add it do variable.

something like
S = 2000000;
SUM = 0;
WHILE S {
SUM += test(s);
SUM--;
}

then it would be O(1) memory complexity

fuck

s/SUM--/S--/g

>now please repeat that in SQL

I might just be retarded, but how is that O(n^2)?
Isn't the inner loop is only called on prime numbers rather than all n numbers?

lmao

That porn video sucked.

look at

memset(prime, true, ubound);

you made array full of Trues. Everything is tru and tru means that if in outter for cycle gets triggered

All the non-primes already have false set by the time the outer for loop reaches them though

What does O(N) even mean? I really could care less but might need it for interview like

u sure? better show me then

Order of complexity
If your input is size N then the computer takes roughly N (times some constant) amount of time to complete.
O(N^2) means that if the input is twice as big, it'll take 4 times longer to execute. etc.

int multiple;
for (multiple = p * 2; multiple

and how is this part member of outter cycle exactly? it still has to jump into that condition

I don't understand what you're trying to say.

ever heard of javascript?

here's something I did back in october
#include
#include
#include
#include

int isPrime(uint32_t n) {
uint32_t mask = n >> 31;
n = (mask ^ n) - mask;

if (n < 4) return 1 % n;
if (!(n & 1)) return 0;

uint32_t i;

for (i = 3; i

Properly implemented sieve should be O(n log log n)
en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Computational_analysis

But there seems to be a problem here in that the inner loop only needs to start at the square of p, and the outer loop can terminate at the square root of ubound.

SELECT SUM(prime) FROM primes WHERE prime < 2000000

Wow that was hard.

I got you, the answer is 7.

Something more like this then?
int sieve(int ubound)
{
int rtubound = sqrt(ubound);
int sum = 0;
bool prime[ubound + 1];
// initialize array with true
memset(prime, true, ubound + 1);

// Mark all composite numbers.
// On the way it finds all the prime numbers below sqrt(ubound), so add those.
int p;
for (p = 2; p < rtubound; p++)
{
// Test if current num is prime
if (prime[p])
{
printf("%d is prime!\n", p);

sum += p;

// Set all multiples of this number to be composite
int multiple;
for (multiple = pow(p, 2); multiple

what language does this?

that's SQL retard

how do you check if a number is prime?

like this guy does prime[p]

but what if you don't have a prime function?

do you have to modulu thing to all of the numbers 2-9?

That's a sql statement that assumes there's already column full of primes

But SQL doesn't have a build in prime table. You would still need to code something to populate a prime table before that

This code works out which numbers are primes as it goes.
Whenever it finds a prime, it marks all the multiples of that number as nonprime.

you check if it's even and larger than 2, then you check if it's divisible by any number smaller than it's square root.

at least that's the most straightforward method. i'm sure there's more sophisticated methods/algorithms.

huh

>smaller than it's square root

wouldn't it be better just to try and divide it by 2-9? isn't dividing let's say 625 by 2-25 a lot more work than just doing 2-9?

121 would be considered prime if you only tested the factors 2 to 9.

oh cuz 11
I see
so no matter what it is a lot of work then

Maybe your database doesn't, but mine does.

I hope you put more effort into your programming than your shitposting

...

def sumprime(list):
start=list[0]
end=list[len(list)-1]
sum=1
for i in list:
if i>1:
v=i
sum+=i
while True:
v+=i
if v>end:
break
list[v-start]=0

return sum

really, faggot? and where do you get the list?

node code:
use as: node script.js 1000000
var len = parseInt(process.argv[2]);
var arr = new Array(len).fill(true);
for(var i = 2; i < arr.length; i++) {
if(arr[i] === true) {
for(var j = Math.pow(i, 2), e = 1; j < len; j = Math.pow(i, 2)+i*e++) {
arr[j] = false;
}
}
console.log('Progress: '+(i/len*100).toFixed(2)+'%');
}

var sum = 0;
for(var i = 2; i < arr.length; i++) {
if(arr[i] === true) {
sum += i;
}
}

console.log('total sum:', sum);

forgot to mention, uses this: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

It's slow because python doesn't have vectors or dumb arrays, only liked lists
start=1
end=2000000
list=[]
for i in range(start,end+1):
list.append(i)

> "straight"
bullshit

am I allowed to import simple mathematical libraries?

Posting my script form last thread:
import math

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

return True

primes = [2,3]

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

if checkprime(i+1):
primes += [i+1]

i += 6

print sum(primes)

for python code, try
def findPrime(maxN):
store=[1]*maxN
summed=0
for x in range(2, int(sqrt(maxN)) ):
if store[x]:
for y in range(x**2, maxN, x):
store[y]=0

for x in range(2,maxN):
if store[x]:
summed+=x
return summed

forgot from math import sqrt

in header

from numpy import log
print(sum([i/log(i) for i in range(2, 2000000)]))

def sum_primes_lt(num):
if num == 2000000:
return 142913828922
else:
raise NotImplementedError

>liked lists
>maybe you mean linked list?
if so, then incorrect. python list is an array-backed list, like the c++ vector
also, try this if you actually need a big list of integers for some reason (python 2):
myList=list(xrange(upperLimit)
(or python 3):
myList=list(range(upperLimit)

Here's my script:
00111110 01001000 01100101 00100000 01110000 01110101 01110100 00100000 01110100 01101000 01101001 01110011 00100000 01101001 01101110 01110100 01101111 00100000 01100001 00100000 01110100 01110010 01100001 01101110 01110011 01101100 01100001 01110100 01101111 01110010 00100000 00110000 00110000 00110001 00110001 00110001 00110000 00110001 00110000 00100000 00110000 00110001 00110000 00110001 00110001 00110001 00110001 00110000 00100000 00110000 00110000 00110001 00110000 00110001 00110000 00110000 00110001

Tanks bro I didn't know about that.

fuck, forgot closing bracket on list()

Why even bother storing values that aren't primes to begin with?

Best answer since it's O(1).

I don't know anything about computer programming stuff, but isn't it jut a matter of

-setting definitions for primes
-setting the limit to 2 million
-letting the computer sort 1~2,000,000 according to definitions of prime numbers
-adding those numbers up

????

>-setting definitions for primes
The definition of a prime is that it has exactly two factors.

If you tackle this problem head on then you're wasting the computer's time calculating shit which isn't necessary.

yeah the first thing you can do is recognize that you don't need to check past sqrt(N).

yes but the problem is with the first step

>I don't know anything about computer programming stuff
Stopped reading there because the rest of your reply is worthless.

total = 0;
for( int i = 0;i

Woops, forgot
; i++

Lolwut? 8has no square, but it's not a prime.

There is not a single formula able to predict prime numbers. That's why calculating them is such a big deal.

You either use a database, or check if every number, individually; is prime or not.

try working on comprehension

Sorry. I just woke up.

improved version because why the fuck not:
console.time('Execution time');
var len = parseInt(process.argv[2]);
var arr = new Array(len).fill(true);
var max = Math.sqrt(len);
for(var i = 2; i < max; i++) {
if(arr[i] === true) {
for(var j = Math.pow(i, 2), e = 1; j < len; j = Math.pow(i, 2)+i*e++) {
arr[j] = false;
}
}
console.log('Progress: '+(i/max*100).toFixed(2)+'%');
}

var sum = 0;
for(var i = 2; i < arr.length; i++) {
if(arr[i] === true) {
sum += i;
}
}

console.log('Total sum:', sum);
console.timeEnd('Execution time');

btw avg execution time for 2mil on this is 73ms

>what is a sieve
/thread

I'm getting an out of range error.

maybe if he got paid a decent amount of money or he's desperate to get into the porn industry

sieve bruh

...

why not only start with odd numbers when you know 2 is a prime?
why start with numbers dividable with 3 when you know 3 is a prime?
why start with numbers dividable with 5 when you know 5 is a prime?
why start with numbers dividable with 127 when you know 127 is a prime?

lol

def divisors(n: Int): List[Int] = for (i isPrime(i)).sum

get rid of your
console.log('Progress: '+(i/max*100).toFixed(2)+'%');
line and tell us how much faster it runs

It's still running...

>why not only start with odd numbers when you know 2 is a prime?
that's actually a good point. instead of checking whether the number is even, it makes more sense to iterate only over odd numbers.

Or instead of doing the pleb method, you could use a sieve as has already been stated by

then it makes more sense to only iterate over the primes
kys

>can't do any of these coding challenge things but manage to pump out apps for a few years
>now managing a team of pajeets and college kids who can do these things
>make more than a few of them combined
kek

Sieveposters are a meme. They can't even verify their results.

I can't into sieve of Eratosthenes, so here is generic attempt.

bool is_prime(int nr) {
if(nr < 2) {
return false;
}
for(int i=2; (i*i)

kys

lol retard

kys

If you can't understand sieve of eratosthenes then watch this gif until it makes sense

But that's wrong.

Iterate over all numbers and just do a prime check...

So any number that's not divisible by 2, 3, 5, 7 is a prime?

It's prime enough for all practical purposes, yes.

No, that's not how it works. Keep watching or read the wikipedia

shut the fuck up, retard.

That way you remove the primes too, because they are dividable by themselves....