• Willkommen im Linux Club - dem deutschsprachigen Supportforum für GNU/Linux. Registriere dich kostenlos, um alle Inhalte zu sehen und Fragen zu stellen.

[Perl] Project Euler

catweasel

Hacker
Hi!

Mit dem Script

Code:
#! /usr/bin/perl -w
use strict;

my %hash = ();

LAB_0: foreach my $b ( 1..9999 ) {
	LAB_1: foreach my $a ( 0..999 ) {
		my $count = -1;
		foreach my $n ( 0..999 ) {
			my $plus = $n ** 2 - $a * $n + $b;
			next LAB_0 if $plus < 1;
			$count++;
			next LAB_1 if is_prime_number( $plus ) == 0;
			$hash{$count} = [ $a, $b ];
		}
	}
}

my $key = 0;
foreach my $k ( sort( { $a <=> $b } keys %hash ) ) {
	$key = $k;
}
print "0  -  ", $key, "       |a| = ", ${$hash{$key}}[0], "   |b| = ", ${$hash{$key}}[1], "\n";

sub is_prime_number {
	return 0 if ( int( $_[0] ) != $_[0]);
	foreach my $divider ( 2..sqrt(  $_[0] ) ) {
		my $quotient = $_[0] % $divider;
		return 0 if ( $quotient == 0 );
	}
	return 1;
}

habe ich versucht das Problem 27 http://projecteuler.net/index.php?section=problems&id=27 zu lösen was mir bisher noch nicht gelungen ist; mit "$n ** 2 - $a * $n + $b" komme ich auf n² - 79n + 1601 und mit "$n ** 2 + $a * $n + $b" auf n² + n + 41. Habe ich einen Fehler im Script, sind die "foreach-Schleifen" zu kurz oder habe ich die Frage nicht richtig verstanden.
 

abgdf

Guru
Hallo,

ein Problem, das ich mit Deinem Code habe, ist, daß Du allmählich fortgeschrittenere Perl-Konstruktionen verwendest, die ich nicht mehr so leicht verstehen kann.
Das ist ein Perl-immanentes Problem, das bei Python übrigens nicht so leicht auftauchen würde (weil es nicht mehr die TMTOWTDI-Philosophie verfolgt).

In

http://projecteuler.net/index.php?section=problems

wird die Aufgabe 27 beschrieben mit:
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
Auf der Seite

http://projecteuler.net/index.php?section=problems&id=27

scheint dann wohl die Lösung dargestellt zu sein ... Du hast beide dort genannten Formeln mit Deinem Skript gefunden, also offenbar die Aufgabe gelöst. Kann mich aber auch irren :kopfkratz: ...

Viele Grüße
 
OP
C

catweasel

Hacker
das ist noch nicht die Lösung.
Im Eingabefeld "Answer" kann man die gefundene Lösung testen, ob sie passt.
 

abgdf

Guru
So, jetzt hab' ich mir das mal genauer angesehen:

1. Man soll nur "n² + an + b", also nicht mit "n² - an + b", rechnen:
Considering quadratics of the form: n² + an + b

2.
where |a| < 1000 and |b| < 1000 where |n| is the modulus/absolute value of n e.g. |11| = 11 and |−4| = 4
Also für a und b von -1000 bis +1000.

Das bedeutet, "n² − 79n + 1601" wird dabei nicht gefunden, weil man für b nur bis +1000 prüft.

Weiterhin ist zu beachten, daß Primzahlen nur natürliche Zahlen sind:

http://en.wikipedia.org/wiki/Prime_number

Unter diesen Bedingungen ist meine Lösung:

n² − 61n + 971

n wird dabei 71.

Hier noch mein Python-Skript dazu:
Code:
#!/usr/bin/env python
#-*- coding: iso-8859-1 -*-

from math import sqrt

def isprime(n):

    if n % 2 == 0 and not n == 2:

        return 0

    else:

        limit = int(sqrt(n)) + 1

        for l in range(3, limit, 2):

            if n % l == 0:
                return 0

        return 1

vals = [0, 0, 0]

print
print "Calculating:"
print "n\ta\tb"

for a in range(-999, 1000, 1):

    for b in range(-999, 1000, 1):

        for n in range(100):

            x = n ** 2 + a * n + b

            if x < 0 or not isprime(x):

                if n > vals[0]:

                    vals = [n, a, b]
                    print str(n) + "\t" + str(a) + "\t" + str(b)

                break

print "\nResult:"
print "n\ta\tb"
print str(vals[0]) + "\t" + str(vals[1]) + "\t" + str(vals[2]) + "\n"
Die Funktion "isprime()" hab' ich aus'm Internet geklaut :).

Lieg' ich richtig ?

Viele Grüße
 
OP
C

catweasel

Hacker
Thx!

War schon mal ziemlich nahe. Das mit den absoluten Zahlen hatte mich durcheinander gebracht und darum habe ich das Produkt ohne Minus eingegeben. Und bei den folgenden Versuchen wurde immer schlechter gelesen :oops: .
 

abgdf

Guru
Hallo,

macht ja nichts. Es ist ein ganz nettes Programmierbeispiel: Da keine Zeiger oder Strings gebraucht werden, geht das auch sehr schön in C:
Code:
#include <stdio.h>
#include <math.h>

/* nr27.c */

int isprime(int n);

int main(void)
{
    int n;
    int a;
    int b;
    int x;

    int vals[] = { 0, 0, 0 };

    printf("\nCalculating:\nn\ta\tb\n");

    for(a = -999; a <= 999; a++)
    {
        for(b = -999; b <= 999; b++)
        {
            n = 0;
            x = pow(n, 2) + a * n + b;

            while(isprime(x))
            {
                n++;
                x = pow(n, 2) + a * n + b;
            }

            if(n > vals[0])
            {
                vals[0] = n;
                vals[1] = a;
                vals[2] = b;

                printf("%d\t%d\t%d\n", n, a, b);
            }
        }
    }

    printf("\nResult:\nn\ta\tb\n");
    printf("%d\t%d\t%d\n\n", vals[0], vals[1], vals[2]);

    return 0;
}


int isprime(int n)
{
    int l;
    int limit;

    if(n < 0)
    {
        return 0;
    }

    if(n % 2 == 0 && n != 2)
    {
        return 0;
    }
    else
    {
        limit = (int) sqrt(n) + 1;

        for(l = 3; l < limit; l += 2)
        {
            if(n % l == 0)
            {
                return 0;
            }
        }

        return 1;
    }
}
Speichern als "nr27.c", kompilieren und starten mit
Code:
gcc -Wall -W -ansi -pedantic -o nr27 nr27.c -lm
./nr27
Mmmh, schön schnell ... :D
Viele Grüße
 
OP
C

catweasel

Hacker
abgdf schrieb:
Die Funktion "isprime()" hab' ich aus'm Internet geklaut :).
Mein isprime ist auch abgeschrieben. Deines läuft bei mir (in Perl geschrieben) aber doppelt so schnell.
So wie dein isprime gab auch meines ursprünglich "1" als Primzahl aus. Ist das so üblich?
Soweit ich gelesen habe, ist "1" keine Primzahl.
 

abgdf

Guru
Hmm, hab' ich so gar nicht drüber nachgedacht. Aber zur Not man kann da ja einfach
Code:
if($n == 1)
{
    return 0;
}
einfügen :wink:.

Viele Grüße
 
Oben