Challenge

How would you implement this, and have the fastest speed possible? I tried this for learning a bit of Rust, but even using a Sieve of Eratosthenes algorithm it takes forever to fetch all the primes. Maybe it's not necessary to fetch all the primes, idk I'm not a mathematician. Wondering how Zig Forums would do at this.


projecteuler.net/problem=3

Attached: screenshot_26.png (1019x617, 719.33K)

Other urls found in this thread:

sciencedirect.com/science/article/pii/S0898122111001131
geeksforgeeks.org/find-largest-prime-factor-number/
hackage.haskell.org/package/safe
en.wikipedia.org/wiki/Integer_factorization#Prime_decomposition

Bring out the big guns sciencedirect.com/science/article/pii/S0898122111001131

You are probably overcomplicating it as a simple brute force finishes in a few milliseconds.
import Safesolve :: Integral a => a -> asolve n = let factor = headMay $ filter ((== 0) . mod n) [2..n - 1] in maybe n (solve . div n) factor

gross dude.
and using that to learn a language is gross.
try Advent of Code instead.:- module eulershit.:- interface.:- import_module io.:- pred main(io::di, io::uo) is det.:- implementation.:- import_module int, list, string.:- func factors(int) = list(int).:- func largest_prime_factor(int) = int.:- pred prime(int::in) is semidet.:- pragma memo(prime/1).main(!IO) :- io.command_line_arguments(Args, !IO), ( Args = [NStr], to_int(NStr, N) -> io.format("largest_prime_factor(%d) = %d.\n", [i(N), i(largest_prime_factor(N))], !IO) ; io.progname_base("factors", Program, !IO), io.format(io.stderr_stream, "usage: %s \n", [s(Program)], !IO), io.set_exit_status(1, !IO) ).largest_prime_factor(N) = largest_prime_factor(N, 2, 1).:- func largest_prime_factor(int, int, int) = int.largest_prime_factor(N, By, P) = F :- ( N = 1 -> F = P ; prime(By), N rem By = 0 -> F = largest_prime_factor(N / By, By, By) ; F = largest_prime_factor(N, By + 1, P) ).factors(N) = factors(N, 2, N / 2).:- func factors(int, int, int) = list(int).factors(N, By, Limit) = L :- ( By >= Limit -> L = [] ; prime(By), N rem By = 0 -> L = [By | factors(N / By, By, Limit)] ; L = factors(N, By + 1, Limit) ).prime(N) :- (N = 1; prime(N, 2, N / 2)).:- pred prime(int::in, int::in, int::in) is semidet.prime(N, By, Limit) :- ( By > Limit ; N rem By \= 0, prime(N, By + 1, Limit) ).wrote a version with factors/1 first. that version is still running. I added largest_prime_factor/1 and tried again. That version gets the answer in 28 ms.

I would google it:
geeksforgeeks.org/find-largest-prime-factor-number/

trace [io(!IO)] (io.format("factor: %d\n", [i(By)], !IO)),
woopsy.factors(N) = factors(N, 2).:- func factors(int, int) = list(int).factors(N, By) = L :- ( N = 1 -> L = [] ; prime(By), N rem By = 0 -> trace [io(!IO)] (io.format("factor: %d\n", [i(By)], !IO)), L = [By | factors(N / By, By)] ; L = factors(N, By + 1) ).output:$ ./eulershit2 600851475143factor: 71factor: 839factor: 1471factor: 6857[71, 839, 1471, 6857]28 ms.

Your use of semicolons is interesting ... I've never seen it, but code looks clean for some reason

A, B

fuck off

#include int main() { fwrite("71 x 839 x 1471 x 6857", 1, 22, stdout);}
the question asks nothing about calculating anything

What language is this?
if it's Haskell, what's 'Safe'?

Haskell.
hackage.haskell.org/package/safe
Safe is a haskell package which takes partial functions from the Prelude and offers total variants of them. For example head from the Prelude is a partial function. If you pass an empty list into head, your program will crash. The Safe package offers a headMay function which will wrap the return type in a Maybe. This means instead of crashing on an empty list, it simply returns Nothing.

Haskell is such a bad meme. Here I rewrote it so you can read it without contracting braindamage: fn solve(n: u64) -> u64 { (2..n).filter(|i| n % i == 0).next() .map_or(n, |i| solve(n / i))}

Without math you'll always be a subpar computer scientist and a low ranking programmer.

sudo apt remove chrome* *google* fonts-noto*
sudo apt remove javascript-common
sudo apt remove rust* libstd-rust* cargo*
sudo apt remove snapd* libsnapd*

You should also do
sudo apt remove apt
sudo apt install guix
sudo apt kys retard

Start with your large number, and divide out (completely) successively larger factors (from 2 onwards). Each divisor you try will necessarily be prime, otherwise one of the previous divisors would have gone into it. It turns out that in this problem, each prime factor only goes in once, ie 600851475143 = p1*p2*p3... all have multiplicity 1, they're not raised to any powers.

71 is the first number to divide into 600851475143, now divide that out,
600851475143 / 71 = 8462696833 If 71 divided in multiple times, we'd repeatedly divide by 71. We now try dividing 8462696833 by 72 onwards. Do you see why 8462696833 couldn't be divisible by any previous factor? Continue this process until the large number is reduced to 1. The last divisor we use will be the greatest prime factor.

600851475143 / 71 = 8462696833
8462696833 / 839 = 10086647
10086647 / 1471 = 6857
6857 / 6857 = 1. [Done]

As you can see, not many divisions are necessary, the number reduces quite quickly.

Pardon me, that should be each proper divisor you try, will necessarily be prime. 72 for instance is not a proper divisor of 8462696833, so you try 73, 74... onwards to 839.

cringe
just link to wikipedia next time
en.wikipedia.org/wiki/Integer_factorization#Prime_decomposition

even easier, just explain what

is doing

Go back to reddit.
I hate you pajeets so fucking much.


Makes sense, thanks.

cope

You are the reason this board sucks.

Oh. NA awake again? What a shame.

Why are you commenting in this thread when you clearly have nothing worthwhile to contribute? Just because you can post here, doesn't mean you should use it as an excuse to brandish your low IQ.

Don't waste your time effort posting here, Zig Forums is a board full of dim ingrates who in all likelihood are probably not even white, or represent the worst of our race at best. For every intelligent poster, there are about 20 who struggle to even install OpenBSD
See:

monthly reminder: whites built an internet in which you can't tell who's white
non-whites funded an internet in which you know not only that, but also how many times people fart in their sleep

Cringe.

based

based

Brain damage isn't one word you obnoxious faggot.

...