andmott has asked for the
wisdom of the Perl Monks concerning the following question:
I'm taking a perl course, and my homework is the following:
"Write a oneliner that is the equivalent of the Unix factor program: it should print out all the prime factors of its input."
It seems a little bit much to ask in my opinion of a oneliner, but what do you think? Part of my question is whether this is a good quiz or not.
I haven't gotten to the oneliner part or 'prime factors' part of the problem yet. I've just been trying to calculate the prime numbers encapsulated within a given number. So far this is what I have.. and it assumes an input of greater than 1 (since its suppose to be one liner I figure you wouldn't use it to compute a number like one or zero) It prints a list of the prime numbers for now.
#!/usr/bin/perl
use strict;
use warnings;
my $x = 7; # Sample Input
my @a;
my @p;
for (my $i = 2; $i <= $x; $i++) {
for (my $z = 2; $z <= $i; $z++) {
push @p, $z unless $i % $z;
}
push @a, pop @p if $#p == 0;
@p = ();
}
print $_, "\n" foreach @a;
I'm going to continue to work on the next section of the problem, but really, do you think this question is a bit much to ask?
Update
Thanks everyone for all of your input and help! I have one final question regarding the example code that moritz was gracious enough to provide (thanks!):
$_ = 1 x shift;
while( /^(11+?)\1+$/ ) {
print length $1;
$_= 1 x ( length() / length $1 )
}
print length;
I think I understand the brilliance behind the regular expression, and turning the number into a string, I just have one question about the math. The regex will match the smallest possible factor, right? Each iteration of the loop it effectively divides the length of the string by the match's length. If it does match the smallest possible factor (or exits the loop and prints the length), then how does it ensure that it only picks prime numbers each time?
Update 2
After reviewing the above code and after hearing back from my instructor, here is my nonawesome version of the same code. It assumes numbers greater than 1 are input.
#!/usr/bin/perl
use strict;
use warnings;
my $x = shift; # some number argument
for ( my $y = 2; $y <= $x; $y++ ) {
next if $x % $y;
$x /= $y;
print $y, "\n";
redo;
}
.. and that in a oneline format looks like
perl le '$x=shift; for($y=2; $y<=$x; $y++) { next if $x%$y; $x/=$y; p
+rint $y; redo }' 7
Thanks everyone!
Re: Calculate prime factors for a given numer in a perl oneliner
by jethro (Monsignor) on Dec 15, 2010 at 17:55 UTC

That depends on a few other factors you don't mention: Is it a beginners course? What functions, operators or methods were teached directly before this homework? Would they be useful tools to solve the problem?
Generally the (mildly) difficult part seems to be to find a useful algorithm/mathematical formula to factor numbers, not the coding part as even your 16 line script will still fit into a single line if you just remove the newlines ;)
PS: I just tried a very straightforward method and without trying to condense it used 91 characters with 8 statements, one of which was a while loop
 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by toolic (Bishop) on Dec 15, 2010 at 17:56 UTC

It seems a little bit much to ask in my opinion of a oneliner, but what do you think? Part of my question is whether this is a good quiz or not.
In my opinion, this problem does not seem like a good candidate for a Perl oneliner solution. A good practical use of a oneliner is to do something quick and dirty on the command line which is too cumbersome with other tools (like grep). Anything more complicated is hardly worth it; just put the code in an file.
That being said, a good impractical (and fun) use of a oneliner is a Perl golf tournament.
 [reply] 
Re: Calculate prime factors for a given number in a perl oneliner
by moritz (Cardinal) on Dec 15, 2010 at 18:20 UTC

$ perl E '$_=1x shift;while(/^(11+?)\1+$/){say length$1;$_=1x(length(
+)/length$1)}say length' 45
3
3
5
There you go, prime factors in increasing size. I'm sure it can be golfed down even further.
 [reply] [d/l] 

I don't think you should have provided an answer, especially one without an explanation. Remember this is a homework problem. We are supposed to be helping the supplicant to reach a solution by giving hints, and insightful analysis of the problem.
For example kennethk pointed out that that there is no need to store prime factors if they will be printed out.
By giving an answer, you did not help the supplicant, you where just showing off.
 [reply] 

chrestomanci:
You've written some very good nodes in the brief time (since Nov of this year; 40some days)... and your view (above) finds support in the Monastery's guidance (so NO   ), but, in this case
you're teaching your grandfather how to suck eggs!
Bishop moritz earned his exalted station, too, and has been here enough longer than you to know the local mores.
So why have I troubled myself to reply?
Because moritz' golfed solution, if submitted by a student to satisfy a homework assignment, would reveal itself immediately as work copied from somewhere, not arrived at independently. (In fact, IMO, sometimes in the wake of a particularly lazy question, such a reply is offered in hopes that that lazy one will plagarize and be caught.)
More often, I suspect, such an answer is offered because it can provide a learning opportunity to the diligent student, even if it does no more than inspire that student to deobfuscate the expert's code.
Update: misspelling corrected
 [reply] 

I respect your opinion, but I kindly disagree.
If the OP wanted to learn something from that solution, a quick google search would have supplied insight to actually understand the solution, and to gain something from it.
I don't see any harm in posting a solution that follows a very different approach to the initial proposal.
 [reply] 

Remember this is a homework problem. We are supposed to be helping the supplicant to reach a solution by giving hints, and insightful analysis of the problem.
If you want it to be a homework problem, and to give insightful analysis, you shouldn't ask for a oneliner, and you shouldn't consider Abigail's (infamous) regexp as an answer. It's obscure, inefficient, uses an unreasonable amount of memory, and quite quickly hits limits.
 [reply] 

 [reply] [d/l] 

I didn't investigate it thoroughly, but I think it's not the nongreediness. Rather the + in the regex is compiled to {1,32767}, which is a general limit of the 16 bit heritage of the regex engine.
 [reply] [d/l] [select] 

 [reply] 

 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by kennethk (Abbot) on Dec 15, 2010 at 18:03 UTC

 [reply] 

Thanks for the feedback and hint I appreciate it!
 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by ww (Archbishop) on Dec 15, 2010 at 20:02 UTC

My answer  to the explicit question "do you think this ... is a bit much to ask?" goes not to the issue of whether the answer would be an appropriate use of Perl, but rather to an atleastplausible interpretation of the question, "do you think this is appropriate homework?"
My answer has to be a resounding "Yes!"  qualified only by the kind of question jethro raised... which, rephrased, might be, "is this too hard for (levelofstudents)?"
Of course, I can't psi the instructor's pedagological intent, but  again, depending on the skill levels expected of students at this stage of the particular course  it seems to me that it might encompass two objectives: 1) encouraging the student to develop (or select) a decent algorithm and 2) to express that in a concise script (oneliner).
 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by Crackers2 (Parson) on Dec 16, 2010 at 02:31 UTC

I think I understand the brilliance behind the regular expression, and turning the number into a string, I just have one question about the math. The regex will match the smallest possible factor, right? Each iteration of the loop it effectively divides the length of the string by the match's length. If it does match the smallest possible factor (or exits the loop and prints the length), then how does it ensure that it only picks prime numbers each time?
Think it through for a minute. Let's start at 2, the first prime; it'll keep finding matches until it's no longer divisible.
Next number is 3; same thing, keep going until it's no longer divisible.
Next _possible_ number is 4... but if 4 would work, then 2 would have worked as well. So it's not going to find any matches.
Next number is 5, prime. Nothing special
Next one, 6... anything that works for 6 would also have worked for 2 and 3, so again it won't find anything.
And you can keep going. There won't be any matches of a nonprime number length, since those would have always been matched by one of the (smaller) prime factors of that number. You might want to look at the Sieve of Eratosthenes to see why this works.
 [reply] 

 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by ysth (Canon) on Dec 15, 2010 at 20:18 UTC

I'm tempted to suggest a oneliner to download, make, and run factor...
 [reply] 
Re: Calculate prime factors for a given numer in a perl oneliner
by dhaval (Initiate) on Dec 20, 2010 at 13:37 UTC

It seems a little bit much to ask in my opinion of a oneliner, but what do you think? Part of my question is whether this is a good quiz or not.
As per my opinion, quiz is used to measure growth in knowledge and/or skills. A positive attempt to solve the quiz will definitely improve the knowledge even is not solved. So in case of oneliner task, It might improve the indepth knowledge of language.
I think I understand the brilliance behind the regular expression, and turning the number into a string, I just have one question about the math. The regex will match the smallest possible factor, right? Each iteration of the loop it effectively divides the length of the string by the match's length. If it does match the smallest possible factor (or exits the loop and prints the length), then how does it ensure that it only picks prime numbers each time?
Yes, Its a brilliant use of regular expression, a string operation to fulfill mathematic task. then how does it ensure that it only picks prime numbers each time?
Please read comment which might help you to understand it
^ # match beginning of string
( # begin first stored group
1 # match a one
1+? # then match one or more ones, minimally.
) # end storing first group
\1+ # match the first group, repeated one or more times
+.
$ # match end of string.
Please read this link http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
It will explain it how it works with example.
But as I believe in solution, so performance comes into my mind and I prefer to do it in mathematical way instead of using a regular expression.
Please check following code which takes less time then others.
$y=shift;
for($i=2;$i<=$y;){
next if$y%$i++;
$y/=$i;
push@x,$i
}
print@{$,=x};
One liner format look like :
$y=shift;for($i=2;$i<=$y;){next if$y%$i++;$y/=$i;push@x,$i}print@{$,
+=x};
 [reply] [d/l] [select] 

Thanks for sharing your knowledge. Kudos for performance based solution
 [reply] 

Just for info, I did the same course. Didn't googled for a solution. I've come with that solution.
Now I'm googling it just to see how other perl user are solving that easy problem :) and what I see is quite interesting (especially this things with regex!!)
It might not be the speediest, but still it might be of some interest to some people!
perl le '$_=2;while($ARGV[0]1){if(!($ARGV[0]%$_)){print$_ ;$ARGV[0]/
+=$_;}else{$_++}}' $1
or in a nononeliner form:
$_=2;
while ($ARGV[0]1) {
if (!($ARGV[0]%$_)) {
print $_ ;
$ARGV[0]/=$_;
} else {
$_++
}
}
Sincerely yours,
Alessandro  [reply] [d/l] [select] 

