Here's a challenge Jow Forums

I don't have to prove anything to you, dumb frog poster. Your challenges mean nothing to me.

> what is multiplicity
> what is prime factor

I can't into maths, I'm not a /sci/entist

Attached: brainlet.png (211x239, 5K)

This thread is sad. Only one solution given so far... This proves that Jow Forums is simply a consumerist shithole colonized by /v/. Maybe instead of screaming about ricing your arch desktop or complaining about being jobless even after writing fizzbuzz in 500 ways, anons here should actually learn about technology. Stop feeling special about how open sores your setup is or how you managed to encrypt and hide your special waifu os.

That's middle school shit

Jow Forums BTFO

>prime factors
>implies a loop
Fuck off

Give a proper example you cunt and I'll do your homework for you.

What's wrong with loops?

I don't like factorization
I mean, how long would it take if the input contains a large factor.. like RSA

Given input number
I make a loop while i < square root of the number
If input number % i is 0 it's a factor
Find the other factor redoing this with input number / i

Shitty code for a similar task
val primes: Stream[Int] = 2 #:: Stream.from(3) .filter {n => primes .takeWhile{_ 1) {
val prime = q.head
while (rest % prime == 0) {
cnts(prime) += 1
rest /= prime
}
q = q.tail
}
cnts.toMap
}

@ Seq(-1, 0, 1, 2, 4, 10, 13, 2500000, 342523457, 7777777) map factors
res1: Seq[Map[Int, Int]] = List(
Map(),
Map(),
Map(),
Map(2 -> 1),
Map(2 -> 2),
Map(2 -> 1, 5 -> 1),
Map(13 -> 1),
Map(2 -> 5, 5 -> 7),
Map(6203 -> 1, 55219 -> 1),
Map(4649 -> 1, 7 -> 1, 239 -> 1)
)

-module(primes).
-export([factors/1]).

factors(Ints) ->
[factorize(N) || N
lists:reverse(factorize(N, 2, floor(math:sqrt(N)), [])).

factorize(1, _X, _Sqrt, Acc) ->
Acc;
factorize(N, X, Sqrt, Acc) when X > Sqrt ->
[N | Acc];
factorize(N, X, Sqrt, Acc) ->
case N rem X of
0 ->
factorize(N div X, X, Sqrt, [X | Acc]);
_ ->
factorize(N, X + 1, Sqrt, Acc)
end.

Example output (pic related):
6> primes:factors([1, 12, 997, 1008, 25, 32, 259, 18446744073709551557]).
[[],
[2,2,3],
[997],
[2,2,2,2,3,3,7],
[5,5],
[2,2,2,2,2],
[7,37],
[18446744073709551557]]

It can deal with edge cases, like square numbers or numbers whose largest prime factor is bigger than their square root, and can factor the largest 64-bit prime in a reasonable amount of time.

Attached: file.png (808x194, 147K)

>edge cases, like square numbers or numbers whose largest prime factor is bigger than their square root
Why would those be edge cases?
>can factor the largest 64-bit prime in a reasonable amount of time.
Bleh
>jvm can't into uint64
Too lazy to BigInt it (not to mention the perf consequences). Sucks when your platform shits the bed w.r.t. sane-perf numerics.
inb4 stackoverflow.com/a/21795129

Which language btw?

To expand the run-length encoding, just flatmap with a .fill:
Seq(-1, 0, 1, 2, 4, 10, 13, 2500000, 342523457, 7777777) map factors map {_ flatMap {case(prime, count) => Seq.fill(count){prime}}}
res2: Seq[collection.immutable.Iterable[Int]] = List(
List(),
List(),
List(),
List(2),
List(2, 2),
List(2, 5),
List(13),
List(2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5),
List(6203, 55219),
List(4649, 7, 239)
)

>Why would those be edge cases?
A number can only have either one or zero prime factors bigger than its square root (e.g. 7 in the case of 21). This means you can optimize dumb brute-force factorization by only checking for prime factors smaller than or equal to the square root of the number in question in the main loop, but you have to remember to check for prime factors bigger than sqrt(n) after the main loop finishes, so it's only an edge case for this algorithm. If I had forgotten that check, my program would have factorized 259 as [7], 997 as [], etc.
Square numbers are an edge case because I could have written When X >= Sqrt instead of When X > Sqrt if I was retarded.

>Bleh
I only mentioned it because the most naive implementation can't do that.

>jvm can't into uint64
But it can. Use Long.remainderUnsigned and Long.divideUnsigned (oh nvm I wrote that before checking your stackoverflow link).

>Which language btw?
Erlang. All integers are arbitrary precision by default, but the VM switches between signed 64-bit integers, unsigned 64-bit integers, or bigints to store them, depending on how big they are.

>you can optimize dumb brute-force factorization by only checking for prime factors smaller than or equal to the square root of the number in question in the main loop
Ah, I see, edge cases for this particular implementation.
I was thinking with my "memoize primes, use them in subsequent checks" hat. Though that trades time concerns for space ones, if we're to consider worst case scenarios.
>But it can
Yup, the sudden drop in readability to use that is a (tiny) barrier to use in certain scenarios. At this abstraction level, I much prefer:
>All integers are arbitrary precision by default, but the VM switches between signed 64-bit integers, unsigned 64-bit integers, or bigints to store them, depending on how big they are.
Neat. Best approach from an (developer's) UX POV, in my opinion, though I'm not familiar with the performance consequences.
CL and Python runtimes did that too, right? Can't remember which other ones did.

>he doesnt do montgomery operations

Attached: 1348599152400.png (281x215, 6K)

>montgomery operations
>Jump to Operation Market Garden
primes... primes never change

>Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large number, and for these cryptosystems, the increased speed afforded by Montgomery multiplication can be important in practice.

>What is [][]?
Please tell me you're pretending.

>while (factor < n)
all factors are

What is this, CS101 homework?
If you cant do this yourself you belong on instead of Jow Forums

>every user screaming go do your own homework or I don't have time
>literally only 3 solutions here
>one user even said he can't factor and another asked what a 2d array is

Attached: annoyedpepe.jpg (306x306, 20K)

> each column contains all the prime factors WITH MULTIPLICITY of its corresponding index in the given array (exclude 1 and the original value)
What the fuck
Give more examples because it certainly doesn't sound like factorization

I've got a solution, but OP should do his own homework. I have a hint for him: think about how you would factor a number on paper, using factor trees. Can you write a program that uses this same method?

niggas be pretending so bad, they can't even write out a 15-liner solution
the absolute STATE of summer g

>what is prime factorization

Attached: amidisabled.png (1585x902, 1.91M)

>given an array of ints
Does it handle numbers

>That insane time complexity.
It should not even count. At least optimize the isprime function.

Enjoy:
import math
def factor(n):
factors = []
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
factors.extend(factor(i))
factors.extend(factor(n // i))
break
if factors == []: return [n]
return factors
def easy(a): return list(map(lambda n: factor(n),a))
print(easy([7,28,36,2847036])) #[[7], [2, 2, 7], [2, 2, 3, 3], [2, 2, 3, 19, 12487]]

Just curious why aren’t you using elixir?

>when only 4 anons came up with a solution in 8 hours
>everyone else says they don't feel like copying and pasting or complains about trivial shit like muh loops or muh primes

Attached: beyondretarded.png (260x270, 23K)