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.
Challenge
Nathaniel Roberts
Matthew Thomas
Bring out the big guns sciencedirect.com
Levi Ross
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
Angel Howard
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.
Andrew Perry
I would google it:
geeksforgeeks.org
Gavin Long
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.
Chase Bailey
Your use of semicolons is interesting ... I've never seen it, but code looks clean for some reason
Ethan Hughes
A, B
Camden Howard
fuck off
Isaac Howard
#include int main() { fwrite("71 x 839 x 1471 x 6857", 1, 22, stdout);}
the question asks nothing about calculating anything
Liam Gray
What language is this?
if it's Haskell, what's 'Safe'?
John Price
Haskell.
hackage.haskell.org
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.
Jackson Gray
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))}
Adam James
Without math you'll always be a subpar computer scientist and a low ranking programmer.
Lincoln Rodriguez
sudo apt remove chrome* *google* fonts-noto*
sudo apt remove javascript-common
sudo apt remove rust* libstd-rust* cargo*
sudo apt remove snapd* libsnapd*
Jose Richardson
You should also do
sudo apt remove apt
sudo apt install guix
sudo apt kys retard
Jason Martinez
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.
Evan Jenkins
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.
Hunter Miller
cringe
just link to wikipedia next time
en.wikipedia.org
Caleb Harris
even easier, just explain what
is doing
Samuel Sanders
Go back to reddit.
I hate you pajeets so fucking much.
Makes sense, thanks.
David Bailey
cope
Jeremiah Sanders
You are the reason this board sucks.
Matthew Cox
Oh. NA awake again? What a shame.
Josiah Parker
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.
Sebastian Campbell
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:
Jace Cox
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
Grayson Bell
Cringe.
Justin Rogers
based
Nolan Edwards
based
Bentley Harris
Brain damage isn't one word you obnoxious faggot.
Ryder Sanchez
...