Thread Primzahlen bis einen festgelegten Wert (21 answers)
Opened by Dominik at 2017-12-13 18:22

hlubenow
 2017-12-17 02:59
#187750 #187750
User since
2009-02-22
875 Artikel
BenutzerIn
[default_avatar]
Noch einen: Was ich eigentlich daran spannend finde, ist:
Angenommen, man prüft, ob 23 durch 2 teilbar ist. Ist es nicht.
Daraus folgt aber, daß der höchste Teiler, den man prüfen muß, 11 ist.
Denn 12 * 2 wäre ja schon drüber.
Wenn man dann auf 3 prüft, reduziert sich der höchstmögliche Teiler auf 7.
Und so weiter.
Man muß also immer weniger prüfen, nicht wie der OP macht, ganz bis 22 rauf.
Ich glaube, das kann man so in Code fassen:
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#!/usr/bin/perl

use warnings;
use strict;

my $num = 11000;
my @primzahlen = ();

sub isPrim {
    my $tocheck = shift;
    my $maxlimit = $tocheck;
    my $isprim = 1;
    my $i;
    for $i (@primzahlen) {
        if ($i > $maxlimit) {
            last;
        }
        if ($tocheck % $i == 0) {
            $isprim = 0;
            print "$tocheck\t$i\t$maxlimit\n";
            last;
        } else {
            $maxlimit = int($tocheck / $i);
        }
    }
    return $isprim;
}

for my $i (2 .. $num) {
    if (isPrim($i)) {
        push(@primzahlen, $i);
        print "$i\n";
    }
}

Ist eigentlich ganz cool, denn das denke ich seit Jahrzehnten jedes Mal, wenn es um Primzahlen geht. :)

View full thread Primzahlen bis einen festgelegten Wert