[Boards: 3 / a / aco / adv / an / asp / b / bant / biz / c / can / cgl / ck / cm / co / cock / d / diy / e / fa / fap / fit / fitlit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mlpol / mo / mtv / mu / n / news / o / out / outsoc / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / spa / t / tg / toy / trash / trv / tv / u / v / vg / vint / vip / vp / vr / w / wg / wsg / wsr / x / y ] [Search | | Home]

Primes under 2000000

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

File: ..png (35KB, 365x367px) Image search: [iqdb] [SauceNao] [Google]
..png
35KB, 365x367px
How does /g/ solve the primes under 2 million test.
>>
>>61809557
Without using a sieve
>>
sieve
>>
File: 15021656812799.jpg (64KB, 777x555px) Image search: [iqdb] [SauceNao] [Google]
15021656812799.jpg
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.
>>
File: g.png (10KB, 577x323px) Image search: [iqdb] [SauceNao] [Google]
g.png
10KB, 577x323px
>>
¯\_(ツ)_/¯

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: [iqdb] [SauceNao] [Google]
1495413456092.jpg
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: [iqdb] [SauceNao] [Google]
1475460351002.jpg
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: [iqdb] [SauceNao] [Google]
1495413456192.jpg
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: [iqdb] [SauceNao] [Google]
1485657345065.png
1MB, 1006x963px
>>61812057
>>
>>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.
>>
>>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: [iqdb] [SauceNao] [Google]
1468304739536.jpg
74KB, 1280x720px
>>61809679
>i <= half
what did he mean by this
>>
>>61812886
He's working for Hitler
Thread posts: 60
Thread images: 10


[Boards: 3 / a / aco / adv / an / asp / b / bant / biz / c / can / cgl / ck / cm / co / cock / d / diy / e / fa / fap / fit / fitlit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mlpol / mo / mtv / mu / n / news / o / out / outsoc / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / spa / t / tg / toy / trash / trv / tv / u / v / vg / vint / vip / vp / vr / w / wg / wsg / wsr / x / y] [Search | Top | Home]
Please support this website by donating Bitcoins to 16mKtbZiwW52BLkibtCr8jUg2KVUMTxVQ5
If a post contains copyrighted or illegal content, please click on that post's [Report] button and fill out a post removal request
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.