 XP is just a number PerlMonks

### Calculate prime factors for a given numer in a perl one-liner

by andmott (Acolyte)
 on Dec 15, 2010 at 17:11 UTC Need Help??

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 one-liner 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 one-liner, but what do you think? Part of my question is whether this is a good quiz or not.

I haven't gotten to the one-liner 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 reg-ex 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 non-awesome 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 one-line 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!

Replies are listed 'Best First'.
Re: Calculate prime factors for a given numer in a perl one-liner
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

Re: Calculate prime factors for a given numer in a perl one-liner
by toolic (Bishop) on Dec 15, 2010 at 17:56 UTC
It seems a little bit much to ask in my opinion of a one-liner, 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 one-liner solution. A good practical use of a one-liner 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 one-liner is a Perl golf tournament.

Re: Calculate prime factors for a given number in a perl one-liner
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.

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.

chrestomanci:

You've written some very good nodes in the brief time (since Nov of this year; 40-some 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 de-obfuscate the expert's code.

Update: mis-spelling corrected

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.

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 home-work problem, and to give insightful analysis, you shouldn't ask for a one-liner, 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.
I hadn't previously encountered this piece of (lateral|perversity of) thought and so I played about with it a bit. I noticed that once the regex encounters a match greater than 2^16 in length it stops matching. (eg run the command with the argument 131072 (2^17) ).

Is this a limit of the non-greedy match in regex that I am encountering?

print "Good ",qw(night morning afternoon evening)[(localtime)/6]," fellow monks."

I didn't investigate it thoroughly, but I think it's not the non-greediness. Rather the + in the regex is compiled to {1,32767}, which is a general limit of the 16 bit heritage of the regex engine.

No, that isn't where the technique originated. That node is just me putting it into a nice (and humorous) context. Abigail certainly demonstrated that technique before I posted that. Google says that it "first appeared" on Usenet.

- tye

Re: Calculate prime factors for a given numer in a perl one-liner
by kennethk (Abbot) on Dec 15, 2010 at 18:03 UTC
I wouldn't say so. I just wrote one up that consisted of a single if-else in a while loop - no fancy special variables or built-ins. It seems to me that your current approach is overthinking the problem a bit. For example, there is no need to store the factors if the whole goal is outputting them, and my solution does not involve precomputing prime numbers.

Giving hints without giving solutions is hard.

Thanks for the feedback and hint I appreciate it!
Re: Calculate prime factors for a given numer in a perl one-liner
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 at-least-plausible 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 (level-of-students)?"

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 (one-liner).

Re: Calculate prime factors for a given numer in a perl one-liner
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 reg-ex 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 non-prime 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.

Thanks I appreciate it!
Re: Calculate prime factors for a given numer in a perl one-liner
by ysth (Canon) on Dec 15, 2010 at 20:18 UTC
I'm tempted to suggest a one-liner to download, make, and run factor...
--
A math joke: r = | |csc(θ)|+|sec(θ)|-||csc(θ)|-|sec(θ)|| |
Online Fortune Cookie Search
Re: Calculate prime factors for a given numer in a perl one-liner
by dhaval (Initiate) on Dec 20, 2010 at 13:37 UTC
It seems a little bit much to ask in my opinion of a one-liner, 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 one-liner task, It might improve the in-depth 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 reg-ex 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?
```  ^                # 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};

Thanks for sharing your knowledge. Kudos for performance based solution
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-1){if(!(\$ARGV%\$_)){print\$_ ;\$ARGV/
+=\$_;}else{\$_++}}' \$1
or in a non-one-liner form:
```
\$_=2;
while (\$ARGV-1) {
if (!(\$ARGV%\$_)) {
print \$_ ;
\$ARGV/=\$_;
} else {
\$_++
}
}
Sincerely yours, Alessandro

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://877318]
Approved by toolic
Front-paged by MidLifeXis
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (3)
As of 2022-10-03 21:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My preferred way to holiday/vacation is:

Results (15 votes). Check out past polls.

Notices?