Primes under 2000000

>>61809557
Without using a sieve

sieve

File: 15021656812799.jpg (64KB, 777x555px) Image search: [Google]

64KB, 777x555px

no sieve

I have it memorized
142913828922
1429 1382 8922

>>61809570
>>61809571
>>61809587
What?

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

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

bool isPrime(int x);

int main(){
    string input;
    int max;

    cout << "Max Number: ";
    getline(cin, input);
    istringstream(input) >> max;


    int num = 1;
    int sum = 0;

    for(int k = 0; k <= max; k++)
    {
        if( isPrime(k) )
            sum += k;
    }
    
    cout << "Sum of all primes under " << max << " is: " << sum << "!" << endl; 
    return 0;
}

bool isPrime(int x){
    if( x == 0 || x == 1 )        // 0 and 1 aren't primes
        return false;
    if( x < 0 )            // no negro numbers in my store
        x *= -1;

    int half = x / 2;

    for( int i = 2; i <= half; i++ )        // can't start at 0 or 1 because then modulo always = 0
    {
        if( x % i == 0)
            return false;
    }

    return true;
}

>>61809679
Delete this unoptimized hooplah right now!!!!

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

>>61809652
>>61809679
>>61809744

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<n :
            if(comb%n!=0):
                return False

            k+=1
            comb = comb * (n - k + 1) // k

    return True

def main():
    i=2
    
    while i<2000000:
        if(aks(int(i))):
            print (str(i))

        i+=1

if __name__ == "__main__":
    main()

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

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

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

>>61809570
>>61809587

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.

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

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

>>61809679
>declaring a function after main
kys immediately

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

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

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

>>61811876
>t. skiddie

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

>>61811865
ada is so cute

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

Can /g/ prove with their code that

2**4423 - 1

is a prime?

>>61811812
>>61811895
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.

File: 1495413456092.jpg (66KB, 728x800px) Image search: [Google]

66KB, 728x800px

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

>>61811913

It's from the original post

File: 1475460351002.jpg (88KB, 895x720px) Image search: [Google]

88KB, 895x720px

>>61811948

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

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

File: 1495413456192.jpg (49KB, 394x358px) Image search: [Google]

49KB, 394x358px

>>61811975
Maki programs in ANIS C my man

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

File: 1485657345065.png (1MB, 1006x963px) Image search: [Google]

1MB, 1006x963px

>>61812057

File: 1887202f1a013bf0da7ac3079b2ae2bb.jpg (243KB, 1119x931px) Image search: [Google]

243KB, 1119x931px

>>61812079

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<=Math.sqrt(primes.length);i++) 
            if(!primes[i])
                for(int j = 2;j*i<primes.length;j++)
                    primes[i*j] = true;
    }
    public static long sum(boolean[] primes) {
        long sum = 0;
        for(int i = 2;i<primes.length;i++)
            if(!primes[i])
                sum+=i;
        return sum;
    }
}

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.

>>61812090
>>61812079
>>61812057
Off yourselves, degenerates.

>>61812110
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 <stdlib.h>
#include <stdio.h>

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.

File: 111df37d929d74b4b124fa3b915501f5.jpg (81KB, 854x895px) Image search: [Google]

81KB, 854x895px

>>61812117
anime formum :^)

>>61812102
>>61812123
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?

>>61812153
>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 >>61811865 sums primes below 2M in just over 20ms

>>61812192
Yes I could also count up to i*i <= primes.length to save from having to do the sqrt.

Without using a sieve and using this function I was able to calculate it in 400ms

public static boolean isPrime(int number) {
    if(number<2) return false;
    if(number==2) return true;
    if(number%2==0) return false;
    for(int i = 3; i * i <= number;i+=2) 
        if(number%i==0) return false;
    return true;
}

>>61812200
>wow thats literally shit and wymyn/pajeet tier
>a sieve such as this >>61811865 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.

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

>>61812340
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 <= sqrt(x)

sqrt(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 <= limit; i += 2 {
                if IsPrime(primes, i) {
                        primes = append(primes, i)
                }
        }
        return primes
}

func GenPrimes(ch chan int) {
        primes := GenToLimit(gsqrt)
        for _, v := range primes {
                ch <- v
        }
        f := func(prms []int, num int, cha chan int) {
                for n := num; n < num+STEP; n++ {
                        if IsPrime(prms, n) {
                                cha <- n
                        }
                }
        }
        for i := primes[len(primes)-1] + 2; i < GLIMIT; i += STEP {
                go f(primes, i, ch)
        }
}

func main() {
        ch := make(chan int, 2*STEP)
        go GenPrimes(ch)

        for v := range ch {
                fmt.Println(v)
        }
}

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

>>61812340
>>61812374
That's a nice improvement; thanks.

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

int isprime (int *parray, int num, int length)
{
  int status = 1;
  
  for (int i = 0; (parray[i] <= (sqrt(num))) && 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 should be 150ms - 200ms now.

>import static g.retards.Primes;

File: 1468304739536.jpg (74KB, 1280x720px) Image search: [Google]

74KB, 1280x720px

>>61809679
>i <= half
what did he mean by this

>>61812886
He's working for Hitler