Wlodzimierz Holsztynski
2005-07-01 12:35:31 UTC
Pogram generujacy liczby pierwsze
metoda Eratostenesa jest jednym
z najprostszych cwiczen w programowaniu.
Jednak dla matematykow jest wygodny.
Zamiast przechowywac na dysku wielkie tabele
liczb pierwszych, wystarczy miec krotki
program. Po pierwsze, tworzy wielkie tabele
tak szybko, ze ne warto ich przechowywac
na stale. Po drugie, taki program moze byc
uzupelniany na rozne sposoby zgodnie z
potrzebami.
Program ponizej oblicza nie tylko liczby
pierwsze, ale takze liczbe roznych dzielnikow
pierwszych dla nieparzystych liczb zlozonych
z danego zasiegu.
Program, mimo ze napisany w Perlu, liczy
na moim "Mac mini" szybko az po 36M (M -- milion),
moze i dalej, ale zatyka sie, gdy ma liczyc liczby
pierwsze az po 64M. Dlatego w oddzielnym poscie
podam wersje, ktora choc wolniej liczy dla mniejszych
zasiegow, to szybciej dla wiekszych, dla ktorych
ponizsza wersja zuzywa za duzo pamieci.
Moja maszyna ma nastepujace parametry:
komputer: Mac mini
System operacyjny: OS X 10.3.9
Procesor: 1.25GHz PowerPC G4
Pamiec: 512MB DDR SDRAM
Cache : 512KB
"Bus speed": 167MHz
Dla policzenia liczb pierwszych p \< S
program na opisanej maszynie zuzywa
t sekund, zgodnie z tabelka ponizej,
ktora w 3' & 4' kolumnie podaje liczbe liczb
pierwszych w danym zakresie oraz ostatnia
z nich:
S t #p ostatnie p
================================
1M 1 78498 999983
4M 6 283146 3999971
16M 25 1031130 15999989
36M 59 2204262 35999993
Przy wczesniejszej okazji zamiast 6s i 59s (patrz
tabelka) program zuzyl odpowiednio 5s i 58s --
bo to zalezy od widzimisie systemu, a raczej
od innych obowiazkow, ktore akurat spelnia.
(Dodam, ze druga wersja policzyla zasieg 64M
w 141s oraz 100M w 223s).
Ponizej podaje kod, pozdrawiam,
Wlodek
#######
#!/usr/bin/perl
# program name -- eratosthenes.pl
# author -- Wlodzimierz Holsztynski, 2005
#
# The program uses the Eratosthenes sieve
# to compute the array of primes up to a
# full square r^2. I use a well known but
# not widely popular version which saves
# half of the memory by running the filter
# only over odd numbers, which are indexed
# by consective natural numbers; odd n
# is coded by floor(n/2).
#
# Possibly the original feature of this
# program is counting of the number of the
# different prime divisors of all the composite
# odd numbers from the given range.
#
# This is not a commercial (industrial)
# quality code but it can be used to write
# several other number theoretical applications.
#
# In its present verion the program displays
# only the number of primes and the last 400
# primes in the given range (or all of them
# if there are fewer than 400 of them). The
# rest of the results are wasted but can be
# easily recovered with a bit of additional
# easy code.
#
# My other similar program uses a bit array,
# hence it is faster when it avoids a usage of
# disk. For small ranges the other code is
# slower, and it does not compute the number
# of prime divisors.
# =======================================
use integer;
print "Enter sqrt of the bound ==> ";
chomp($r=<>);
$start = times();
($extra = $r&1)++;
$upBd = ($r*$r - $extra)/2;
#---- sieve ----#
for ($p=3; $p < $r; $p += 2)
{ $d = ($p>>1);
if(!$comp[$d])
{ push @primes,$p;
for ($n=$d+$p; $n <= $upBd; $n += $p) { ++$comp[$n] }
} }
for(((1+$r-$extra)/2)..$upBd)
{ push @primes,2*$_+1 if !$comp[$_] }
#----- end of sieve -----#
$endT = times();
(($disp = @primes - 400) > 0) || ($disp=0, printf "\n %8u",2);
print"\n",' 'x(9*($disp%10));
for ($disp..(@primes-1))
{ print "\n" if !($_%10);
print "\n" if !($_%100);
printf " %8u", $primes[$_]
}
print "\n\n *** There are ", @primes+1," primes < ",$r*$r,"\n\n";
print "Duration of the execution in seconds: ", $endT-$start, "\n\n"
metoda Eratostenesa jest jednym
z najprostszych cwiczen w programowaniu.
Jednak dla matematykow jest wygodny.
Zamiast przechowywac na dysku wielkie tabele
liczb pierwszych, wystarczy miec krotki
program. Po pierwsze, tworzy wielkie tabele
tak szybko, ze ne warto ich przechowywac
na stale. Po drugie, taki program moze byc
uzupelniany na rozne sposoby zgodnie z
potrzebami.
Program ponizej oblicza nie tylko liczby
pierwsze, ale takze liczbe roznych dzielnikow
pierwszych dla nieparzystych liczb zlozonych
z danego zasiegu.
Program, mimo ze napisany w Perlu, liczy
na moim "Mac mini" szybko az po 36M (M -- milion),
moze i dalej, ale zatyka sie, gdy ma liczyc liczby
pierwsze az po 64M. Dlatego w oddzielnym poscie
podam wersje, ktora choc wolniej liczy dla mniejszych
zasiegow, to szybciej dla wiekszych, dla ktorych
ponizsza wersja zuzywa za duzo pamieci.
Moja maszyna ma nastepujace parametry:
komputer: Mac mini
System operacyjny: OS X 10.3.9
Procesor: 1.25GHz PowerPC G4
Pamiec: 512MB DDR SDRAM
Cache : 512KB
"Bus speed": 167MHz
Dla policzenia liczb pierwszych p \< S
program na opisanej maszynie zuzywa
t sekund, zgodnie z tabelka ponizej,
ktora w 3' & 4' kolumnie podaje liczbe liczb
pierwszych w danym zakresie oraz ostatnia
z nich:
S t #p ostatnie p
================================
1M 1 78498 999983
4M 6 283146 3999971
16M 25 1031130 15999989
36M 59 2204262 35999993
Przy wczesniejszej okazji zamiast 6s i 59s (patrz
tabelka) program zuzyl odpowiednio 5s i 58s --
bo to zalezy od widzimisie systemu, a raczej
od innych obowiazkow, ktore akurat spelnia.
(Dodam, ze druga wersja policzyla zasieg 64M
w 141s oraz 100M w 223s).
Ponizej podaje kod, pozdrawiam,
Wlodek
#######
#!/usr/bin/perl
# program name -- eratosthenes.pl
# author -- Wlodzimierz Holsztynski, 2005
#
# The program uses the Eratosthenes sieve
# to compute the array of primes up to a
# full square r^2. I use a well known but
# not widely popular version which saves
# half of the memory by running the filter
# only over odd numbers, which are indexed
# by consective natural numbers; odd n
# is coded by floor(n/2).
#
# Possibly the original feature of this
# program is counting of the number of the
# different prime divisors of all the composite
# odd numbers from the given range.
#
# This is not a commercial (industrial)
# quality code but it can be used to write
# several other number theoretical applications.
#
# In its present verion the program displays
# only the number of primes and the last 400
# primes in the given range (or all of them
# if there are fewer than 400 of them). The
# rest of the results are wasted but can be
# easily recovered with a bit of additional
# easy code.
#
# My other similar program uses a bit array,
# hence it is faster when it avoids a usage of
# disk. For small ranges the other code is
# slower, and it does not compute the number
# of prime divisors.
# =======================================
use integer;
print "Enter sqrt of the bound ==> ";
chomp($r=<>);
$start = times();
($extra = $r&1)++;
$upBd = ($r*$r - $extra)/2;
#---- sieve ----#
for ($p=3; $p < $r; $p += 2)
{ $d = ($p>>1);
if(!$comp[$d])
{ push @primes,$p;
for ($n=$d+$p; $n <= $upBd; $n += $p) { ++$comp[$n] }
} }
for(((1+$r-$extra)/2)..$upBd)
{ push @primes,2*$_+1 if !$comp[$_] }
#----- end of sieve -----#
$endT = times();
(($disp = @primes - 400) > 0) || ($disp=0, printf "\n %8u",2);
print"\n",' 'x(9*($disp%10));
for ($disp..(@primes-1))
{ print "\n" if !($_%10);
print "\n" if !($_%100);
printf " %8u", $primes[$_]
}
print "\n\n *** There are ", @primes+1," primes < ",$r*$r,"\n\n";
print "Duration of the execution in seconds: ", $endT-$start, "\n\n"
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/