Primes under 2000000

How does Sup Forums solve the primes under 2 million test.

Without using a sieve

sieve

no sieve

I have it memorized
142913828922
1429 1382 8922

What?

Here is my attempt I wrote in a few minutes. I got 1179908154.
#include
#include
#include

using namespace std;

bool isPrime(int x);

int main(){
string input;
int max;

cout > max;


int num = 1;
int sum = 0;

for(int k = 0; k

Delete this unoptimized hooplah right now!!!!

Ehh I wrote it in like 3-4 minutes, I just want to know if I got the right answer. I'm still a student working towards that meme degree and saw that whiteboard thread the other day.

I changed the sum variable to a long instead of an int and now I'm getting 142913828922.

...

¯\_(ツ)_/¯

def aks(n):
k=1
comb=n

while k

Look it up on the internet. Lists of at least the first 2 million are available. O(1)

why do it sensibly when you could make two million lines of IF statements and hardcode the list

>he's unable to verify this list
>primality tests run slower than sieves
So might as well sieve for it. Are you too stupid to write a trivial algorithm that is basically marking of multiples of primes?

import Data.Numbers.Primes
main = print (sum (takeWhile (< 2000000) primes))


142913828922

def gen_primes(limit):
if limit >= 2:
yield 2
for i in range(3, limit + 1, 2):
if not any(i % j == 0 for j in range(3, int(i**0.5) + 1, 2)):
yield i

print(sum(gen_primes(2*10**6)))

$ time python3 trial_division.py
142913828922

real 0m12.703s
user 0m12.692s
sys 0m0.008s
This is grade school-tier math. And trial division is slow, no going around it - it's worst case.

5 min coding + 1 min runtime vs 15 min coding + 30s runtime
>B-but how does it scale
You can think about that later.

It scales that in the next time you approach the problem, you will have it optimized from the get-go, you braindead codemonkey.

>declaring a function after main
kys immediately

this
>I want to get better
>but I don't want to try harder
enjoy your blue collar job

In code.

with a sieve
any other method is just plain retarded

-- SIEVE OF ERATOSTHENES
--
with Ada.Text_IO, Interfaces, Ada.Command_Line, Ada.Calendar;
use Interfaces, Ada.Calendar;

procedure sumprimes is
start : Time := Clock;
dur : Duration;
upTo : Unsigned_64 := Unsigned_64'Value(Ada.Command_Line.Argument(1));
prime : array (1..upTo) of Boolean := (1 => False, others => True);
base : Unsigned_64 := 2;
sumOf : Unsigned_64 := 0;
count : Unsigned_64;
begin
while base * base < upTo loop
if prime(base) then
count := base + base;
while count < upTo loop
prime(count) := False;
count := count + base;
end loop;
end if;
base := base + 1;
end loop;

for i in prime'Range loop
if prime(i) then
sumOf := sumOf + Unsigned_64(i);
end if;
end loop;
dur := Clock - start;
Ada.Text_IO.Put("Sum of primes LEQ" & Unsigned_64'Image(upTo) & " is:");
Ada.Text_IO.Put(Unsigned_64'Image(sumOf)); Ada.Text_IO.New_Line;
Ada.Text_IO.Put("Time: " & Duration'Image(dur));
end sumprimes;

LOL

I'd find a function online that tests a number for being a prime efficiently, then add up all the numbers that pass the prime test.

Why reinvent the wheel

I could sum them if I had them

>t. skiddie

You can optimise it when you need it to be better. Low hanging fruit principle. No need to overengineer shit when you don't need to. Stop wasting company time with your autism.

ada is so cute

Nobody would be impressed by this response. You might as well say "I can't do it".

Can Sup Forums prove with their code that 2**4423 - 1 is a prime?

Degenerate. Retarded pajeet tier devs like you are the reason everything is poorly optimized these days and needs overpriced hardware. The quality of code has decreased so badly over the years.

i know! which who in Love Live would program using Ada you think?
i'd say kotori maybe

It's from the original post

...

is no one really going to point out the fundamental problem with your code's runtime?

its a mersenne prime, no?
maybe ill write a proof for you in an hour or two, just woke up

nummies = 0

for numbers in range(1,2000000):
for morenumbers in range(1,2000000):
if numbers % morenumbers != 0:
nummies += numbers

print(nummies)

easy

Maki programs in ANIS C my man

I'm a physicist though. If I run code once I don't care if it's o(x^2) or o(x log x). Most of the time, unoptimisable code needs less time to run than the optimisation process. And even if I have to wait a while, I can do other work while I wait for my pc. My time is worth more than CPU time.

This doesn't apply if your code literally runs on billions of machines, multiple times per day and if the user has to wait for the result and can't do anything else. But the question here wasn't "calculate arbitrarily large prime numbers an arbitrary number of times" but just this one task. Code optimisation is for compilers and code monkeys.

...

...

This is a simple sieve that can be used to solve it in 25ms.
public class Primes {
public static void sieve(boolean[] primes) {
for(int i = 2;i

if I know the input size to be checked is small I do a factor check because it's so easy to write. Bigger input sizes require writing up a sieve which I have to look up references for because I can't remember how to do them on a whim.

Off yourselves, degenerates.

Sieves are literally just prime factors being applied to an array as opposed to a single number.

He's my single threaded one in C from a thread a while ago. I'll eventually multi-thread it; just not now so early in the morning.

#include
#include

int isprime (int *parray, int num, int length)
{
int status = 1;

for (int i = 0; (parray[i] < (num/2)) &&i < length; 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);
}


Runtime for 1-2M should be 15-25s depending on your CPU.

anime formum :^)

nice. couldn't you set j = i in the second loop of the sieve to avoid doing 2*3 and then later 3*2 and so on?

>Runtime for 1-2M should be 15-25s depending on your CPU.
wow thats literally shit and wymyn/pajeet tier

a sieve such as this sums primes below 2M in just over 20ms

Yes I could also count up to i*i

Without using a sieve and using this function I was able to calculate it in 400ms
public static boolean isPrime(int number) {
if(number

>wow thats literally shit and wymyn/pajeet tier
>a sieve such as this sums primes below 2M in just over 20ms
The original thread for which I wrote that for had the added condition of "try to do it yourself; don't look anything up".

I don't have a sieve of eratosthenes for summing primes memorized, so I wrote something simple and easy to understand.

You could dramatically improve your algorithm by counting up to and including the square root instead. Think of it like this. For every divisor under the square root their must be some corresponding divisor above it aswell. Thus if you still haven't found a divisor after having reached the square root you're not going to find one.

Or if you'd prefer

Let m be a divisor of x and m be less than or equal the sqrt(x)

Let n be equal to x/m

Therefore

m = x/n

x/n

package main

import (
"fmt"
"math"
)

const (
GLIMIT int = 2000000
STEP int = 5000
)

var gsqrt int = int(math.Sqrt(float64(GLIMIT)))

func IsPrime(primes []int, num int) bool {
sqrt := int(math.Sqrt(float64(num)))
for _, v := range primes {
if num%v == 0 {
return false
}
if v > sqrt {
break
}
}
return true
}

func GenToLimit(limit int) []int {
primes := make([]int, 0, 255)
primes := append(primes, 2)
for i := 3; i

multithreaded, saves memory and finishes around 400ms, but terminates with deadlock panic

That's a nice improvement; thanks.

#include
#include
#include

int isprime (int *parray, int num, int length)
{
int status = 1;

for (int i = 0; (parray[i] = 2)
sum += 2;

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

free(parray);
exit(EXIT_SUCCESS);
}


Runtime should be 150ms - 200ms now.

>import static g.retards.Primes;

>i

He's working for Hitler