This is a blue board which means that it's for everybody (Safe For Work content only). If you see any adult content, please report it.

Thread replies: 60

Thread images: 10

Thread images: 10

OP

Primes under 2000000 2017-08-09 03:12:56 Post No. 61809557

[Report] Image search: [iqdb] [SauceNao] [Google]

Primes under 2000000 2017-08-09 03:12:56 Post No. 61809557

[Report] Image search: [iqdb] [SauceNao] [Google]

How does /g/ solve the primes under 2 million test.

>>

>>61809557

Without using a sieve

>>

sieve

>>

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

>>61809587def 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 that2**4423 - 1is 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.

>>

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

>>

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

>>

>>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: 1887202f1a013bf0da7ac3079b2ae2bb.jpg (243KB, 1119x931px) Image search:
[iqdb]
[SauceNao]
[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:
[iqdb]
[SauceNao]
[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 400mspublic 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;

>>

>>61809679

>i <= half

what did he mean by this

>>

>>61812886

He's working for Hitler

Thread posts: 60

Thread images: 10

Thread images: 10

If a post contains copyrighted or illegal content, please click on that post's

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the content originated from that site. This means that 4Archive shows an archive of their content. If you need information for a Poster - contact them.