I got one!!!

[Strike]

To stoke the fires of cf.net I have come up with another simple challenge for people to have fun with. It's actually REALLY simple, but I thought it might be a good chance for people trying new languages (that is what you all have been doing since you haven't been doing any new challenges, right?) to try out their new knowledge.

The project is simply: a prime factorization tool. Input is in format of your choice, output is in format of your choice.

Bonus points for the following:
* (BIG FAT BONUS POINTS) GUI
* (extra big fat bonus) GUI with a non-text (graphical) tree output of the result
* parses a file and displays many results for all the numbers in the file (format of your choosing)
* asking the user for a number until they choose to quit
* taking a number or numbers as an arugment on the command line
* displaying a tree output instead of some boring list of primes
* a more intelligent algorithm than brute forcing by dividing by every number up to the one being tested (hint: if you are checking to see if 11 is prime, once you get to 4 you don't need to check any higher numbers; or the more obvious hint: even numbers aren't good prime factors [with one exception])
* a progress indicator as it works out the primes for each (presumably only really important for factoring large numbers)
* timing each factorization
* unit tests! (using a decent sized set of known prime factorizations, etc., test and make sure your algorithm works as expected)

Okay, so now you see all the possibilities this simple task can have - go to it!

[Strike]

Okay, I've got a good start.
I even earned some bonus points ;)

Before I get to the code, keep in mind that this was optimized for speed in factoring entire lists of numbers, and not for code cleanliness :) I think it's still relatively easy to follow though. Just a couple of not-necessarily-obvious logic areas that I should comment. But here we go, my factorizer. It just factorizes 2 through 500 by default.

http://strike.homelinux.org:81/~ddipaolo/prime-challenge/primes.py

Here's the results I get when I profile it on a P3-450:

<buncha output>
2371 function calls in 0.540 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.450 0.450 <string>:1(?)
498 0.020 0.000 0.020 0.000 primes.py:12(generate_primes)
1371 0.190 0.000 0.210 0.000 primes.py:28(is_prime)
498 0.170 0.000 0.380 0.001 primes.py:45(factor)
1 0.040 0.040 0.420 0.420 primes.py:63(factor_list)
1 0.030 0.030 0.450 0.450 primes.py:70(main)
1 0.090 0.090 0.540 0.540 profile:0(primes.main())
0 0.000 0.000 profile:0(profiler)

[Bradmont]

a prime factorization program?

ok:


#!/usr/bin/env python

num = raw_input()
print "1, " , num


OH! You meant a program to calculate prime factors, not a program to factor primes! :p

[Strike]

Yes, that is known is prime factorization.

[Strike]

Ah, come on, with 62 views at least some of you others have read this. And I count 18 views (that aren't me :)) to my source! Where's the love?

[kmj]

I still love you Strike; I'm just a lazy turd. Plus I think the summer weather has damped the coding fury in many of us.

[madMoney]

hey guys, this is my first post on CF.net. I love reading this competitions board :). Glad to finally participate

I'm in the process of learning java, so any java experts out there (dru :)?) please pick it apart and let me know what i did right/wrong.

Prime Calculator Class - http://users.nexet.net/danadler/java/pcalc.java.txt (http://users.nexet.net/danadler/java/pcalc.java.txt)

Number Class - http://users.nexet.net/danadler/java/num.java.txt (http://users.nexet.net/danadler/java/num.java.txt)

It's pretty weak right now, but I'll keep updating the files. Here's some sample output:


java pcalc 25098099 257 910
25098099:
3 *
13 *
37 *
17393
This calculation took 2 milliseconds.

257:
257
This calculation took 0 milliseconds.

910:
2 *
5 *
7 *
13
This calculation took 1 milliseconds.


thx to Dru for his timer code

also, Strike, could I see an example of graphical output?

[Strike]

madMoney (I want to type Monkey so bad when I see that), I'll try and whip something up, but it probably won't happen tonight. Basically, the idea was to either do it ASCII art style like:

910 25098099 9
/ \ / \ / \
2 455 3 8366033 3 3
/ \ / \
5 91 13 643541
/\ / \
7 13 37 17393

Or to actually perhaps use some other methods to actually draw text somewhere with a sort of tree representation. Maybe using a tree widget, or maybe actually using image rendering stuff.

[madMoney]

phew, that was tough, but I got the program working

I've updated the files that I linked earlier to the new source
Unfortunately at times this turned into a guess-and-check operation, so my code's not the prettiest you've ever seen.

anyway, here's some sample output:


java pcalc 25098099 257 910
25098099
/ \
3 8366033
/ \
13 643541
/ \
37 17393
This calculation took 2 milliseconds.

257
This calculation took 0 milliseconds.

910
/ \
2 455
/ \
5 91
/ \
7 13
This calculation took 0 milliseconds.


anyone else feel like solving this one? :P