Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Perl vs. Python for prime numbers

by Anonymous Monk
on Jun 13, 2013 at 21:22 UTC ( [id://1038843]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi Monks, looking for a compare between Perl vs Python

I am going to replace this Python code

for n in range(2, 100): for x in range(2, n): if n % x == 0: #print(n, 'equals', x, '*', n//x) break else: print(n, 'is a primer number')
with something similar using old perlish good code...
How could emulate the else: clause of the loop?
Something better than
for $i (2..100){ $p=0; for $j (1..$i){ if($i % $j==0){ $prime_[$p] = "$j"; $p++; } if ($prime_[1] == $i){ print "$i is a primer number\n"; } } }

Replies are listed 'Best First'.
Re: Perl vs. Python for prime numbers
by BrowserUk (Patriarch) on Jun 13, 2013 at 22:24 UTC

    Maybe not the point of your post, but that is one dumb algorithm for finding primes.

    Why test even numbers greater than 2? Why test multiples of the primes already found? Why trial divide with Xs greater than sqrt(n)?


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      The algorithm is lifted straight from the standard Python documentation, presumably as a toy example to illustrate the quirky "else" clause of Python loop statements.

        Ug. Those docs sum up my feelings exactly:

        (Yes, this is the correct code. Look closely: the else clause belongs to the for loop, not the if statement.)

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Perl vs. Python for prime numbers
by choroba (Cardinal) on Jun 13, 2013 at 21:35 UTC
    I was able to transfer the logic using a block with last:
    #!/usr/bin/perl use warnings; use strict; use feature qw(say); for my $n (2 .. 99) { PRIME: { for my $x (2 .. $n - 1) { last PRIME if 0 == $n % $x; } say $n, ' is a primer number'; } }

    Update.
    But I would rather use something like the following:

    for my $n (2 .. 99) { my $is_prime = 1; $is_prime &&= $n % $_ or last for 2 .. sqrt $n; say $n, ' is a primer number' if $is_prime; }

    Update 2: &&= used instead of *= to avoid large numbers.

    لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
      > $is_prime &&= $n % $_ or last for 2 .. sqrt $n;

      why so complicated, isn't a simple flag sufficient?

      #!/usr/bin/perl use warnings; use strict; use feature qw(say); for my $n (2 .. 99) { my $prime = 1; for (2 .. $n-1) { $prime = 0, last unless $n % $_; } say $n, ' is a primer number' if $prime; }

      Cheers Rolf

      ( addicted to the Perl Programming Language)

Re: Perl vs. Python for prime numbers
by LanX (Saint) on Jun 13, 2013 at 23:14 UTC
    OK no comment about the algorithm, I take this as a constructed case for comparison of two languages.

    The first approach is a variation of chorobas code, but a bit more intuitive from my perspective.

    The second is a generic approach using goto. This technique can always emulate this (very) Python idiom.

    #!/usr/bin/perl use warnings; use strict; use feature qw(say); N: for my $n (2 .. 99) { for my $x (2 .. $n - 1) { next N if 0 == $n % $x; } say $n, ' is a prime number'; } for my $n (2 .. 99) { for my $x (2 .. $n - 1) { goto NOT_PRIME if 0 == $n % $x; } say $n, ' is a prime number'; NOT_PRIME: }

    I think both are pretty good readable.

    HTH! =)

    Cheers Rolf

    ( addicted to the Perl Programming Language)

      I observe that your inner loop only runs to $n - 1 while in the Python script it runs to n. The former makes sense to me but the latter not. I know little about Python, but running the inner loop to n should produce no primes found at all. Why does it work anyway (I checked it does)? I guess this is off topic as it is a Python question...

        I observerd that too, so I ran python and tried
        print(range(1,10))

        Lo and behold:

        [1, 2, 3, 4, 5, 6, 7, 8, 9]
        لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
        Actually I copied choroba's code w/o caring about the difference, but yes, as he already showed, the range built-in in Python excludes the upper bound.

        Makes sense from a mathematical point of view (combining different ranges is easier) but I prefer the more intuitive Perl way to do it.

        Cheers Rolf

        ( addicted to the Perl Programming Language)

      As a side note: Python has no labels, and loop control statements like break are restricted to the inner loop.

      So this "natural" solution in Perl (that is w/o flag variable) isn't possible in Python

      N: for my $n (2 .. 99) { for my $x (2 .. $n - 1) { next N if 0 == $n % $x; } say $n, ' is a prime number'; }

      Looking at a one to one translation of the flow, it bugs me that the "NOT_PRIME" part is executed after the "PRIME" part, which is quite strange in my eyes

      for my $n (2 .. 99) { for my $x (2 .. $n - 1) { goto NOT_PRIME if 0 == $n % $x; } PRIME: say $n, ' is a prime number'; NOT_PRIME: }

      So to separate code which doesn't belong to the py-else branch one needs to put it into the loop into the py-if branch

      so the logic of this Perl code with flag-var prime

      for my $n (2 .. 99) { my $prime = 1; for (2 .. $n-1) { $prime = 0, last unless $n % $_; } if ($prime) { print $n, " is "; } else { print $n, " is not "; } print "a prime number\n"; }

      translates to

      for my $n (2 .. 99) { for my $x (2 .. $n - 1) { if (0 == $n % $x) { # py-if branch print $n, " is not "; goto BREAK; # py-break } } print $n, " is "; # py-else branch BREAK: print "a prime number\n"; }

      I think now the motivation to call this statement "else" it's better understandable. But the py-docs do not seem to provide any such motivation.

      Maybe it's a matter of practice, but I rather prefer the ability to have Perl labels and loop controls like next or last to address them.

      And Perl's goto still gives me the freedom to emulate any python code in a 1-to-1 translation. And the naming of the label in Perl gives me additional freedom to clarify the code! ¹

      Python OTOH can't emulate labels or Perl's control flow and needs to redesign the code when migrated.

      See also this SO- discussion http://stackoverflow.com/questions/438844/is-there-a-label-goto-in-python for how quirky and complicated py-workarounds can become...

      Cheers Rolf

      ( addicted to the Perl Programming Language)

      ¹) Please note that I named the "BREAK:"-label as "NOT_PRIME:" in my first post, thats very self-commenting and easier to understand than simply "else:"

Re: Perl vs. Python for prime numbers
by hdb (Monsignor) on Jun 14, 2013 at 06:59 UTC

    Just for completeness, check the "short" solutions posted here: Re^3: Fibonacci Sequence. The title says it is on Fibonacci sequences but this post is offering prime numbers.

    More seriously:

    use strict; use warnings; my @primes; PRIME: for my $n (2..100) { for my $p (@primes) { next PRIME unless $n % $p; } push @primes, $n; } print "@primes\n";
Re: Perl vs. Python for prime numbers
by Anonymous Monk on Jun 13, 2013 at 22:01 UTC
    Why aren't you guys limiting $x to sqrt($n)+1 ?
Re: Perl vs. Python for prime numbers
by pvaldes (Chaplain) on Jun 15, 2013 at 10:50 UTC

    This is a message from "saving electrons for better purposes.org"

    my @perfectly_well_known_prime_number_under_thousand = (2, 3, 5, 7, 11 +, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, + 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 1 +57, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, +233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, + 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397 +, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 47 +9, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 5 +77, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, +659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, + 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 +, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 94 +7, 953, 967, 971, 977, 983, 991, 997); foreach (@perfectly_well_known_prime_number_under_thousand){ print $_," is a prime number and everybody knows it. I will not spend +CPU cycles in vain\n"}

    (I bet that this is faster...) ;-)

      We could save typing and electrons:
      use Math::Prime::Util qw/forprimes/; forprimes { say } 1000; # optionally takes range a,b
      OK, it's cheating using modules. But it's easy, and it also uses a segmented sieve so should be efficient even with large values (e.g. list the primes between 10**18 and 10**18+100000), and works with bigints too.

      Some Python ways to do this, all of which are *much* faster than the OP code when we want anything more than tiny values like 1000. There are probably even better ways.

      Using sympy. Much slower than the Perl module:

      from sympy import sieve for i in sieve.primerange(2,1000): print i

      using gmpy2 (only ~2x slower than the Perl module):

      import gmpy2 n = 2 while n <= 1000: print n n = gmpy2.next_prime(n)

      Or some Python by hand that is very fast:

      from math import sqrt, ceil def rwh_primes(n): # http://stackoverflow.com/questions/2068372/fastest-way-to-list-a +ll-primes-below-n-in-python/3035188#3035188 """ Input n>=6, Returns a list of primes, 2 <= p < n """ correction = (n%6>1) n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6] sieve = [True] * (n/3) sieve[0] = False for i in xrange(int(n**0.5)/3+1): if sieve[i]: k=3*i+1|1 sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1 +) sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*( +i&1))/6-1)/k+1) sieve[n/3-correction] = False # If you want the count: return 2 + sum(sieve) return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve +[i]] for i in rwh_primes(1000): print i
Re: Perl vs. Python for prime numbers
by jakeease (Friar) on Jun 14, 2013 at 11:45 UTC

    not the shortest one... :-)

    EDIT: but it does hold the loop to sqrt of $last...

    #!/usr/bin/perl use warnings; use strict; use feature qw(say); my $last = 1000; my @num = (2..$last); for my $i (@num) { $num[$i] = 1; } for (my $i=2; $i*$i <= $last; $i++) { if ($num[$i]) { for (my $j=$i; $j*$i < $last; $j++) { $num[$i * $j] = 0; } } } my @prime = (); for (my $i=2; $i<=$last; $i++) { if ($num[$i]) { push @prime, $i; } } say "@prime";

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1038843]
Approved by davido
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2024-03-29 12:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found