利用者:1yen
メモ書きです。はい。 エラトステネスの篩の実行時間を計測 lua-5.3.3 を使用 -- エラトステネスの篩
-- 1000000000 まで
local prime_max=100000000
-- prime をテーブル型として宣言
-- 素数の場合 nil 素数でない場合 false とする
local prime = {}
local i
local t_start = os.clock()
for i=2, prime_max/2 do
-- 素数を見つけたら、その倍数には「素数でない (false)」とマーク
if prime[i] == nil then
for j=i+i, prime_max, i do
prime[j]=false
end
end
end
local t_end = os.clock()
print("elapsedTime : " .. t_end - t_start .. "(sec)")
-- 求められた素数の最大値を表示
i=prime_max
repeat
i = i - 1
until (prime[i] == nil)
print (string.format("PRIME MAX: %d", i))
Bywater BASIC 3.0 を使用 10 REM INT の範囲は -999999 ～ 0 ～ 999999
100 DEFINT I-J,P
110 P_MAX=999999
120 DIM PRIME(P_MAX)
130 S_TIME$=TIME$
140 PRINT "START ";S_TIME$
150 FOR I=2 TO P_MAX
160 IF PRIME(I)=0 THEN
170 FOR J=I+I TO P_MAX STEP I
180 PRIME(J)=1:REM 素数で無いとマーク
190 NEXT J
200 REM PRINT I:REM 求まった素数を表示
210 END IF
220 NEXT I
230 E_TIME$=TIME$
240 PRINT "END ";E_TIME$
250 S_TIME=(VAL(S_TIME$)*60 + VAL(MID$(S_TIME$,4)))*60 + VAL(RIGHT$(S_TIME$,2))
260 E_TIME=(VAL(E_TIME$)*60 + VAL(MID$(E_TIME$,4)))*60 + VAL(RIGHT$(E_TIME$,2))
270 PRINT USING "elapsedTime: #####&"; E_TIME-S_TIME, "sec"
280 FOR I=P_MAX TO 2 STEP -1
290 IF PRIME(I)=0 THEN EXIT FOR
300 NEXT I
310 PRINT "PRIME MAX: ";I
gcc を使用 #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
/****
gcc -pg -march=core-avx-i -O2 -o a_MAX.exe Eratosthenes.c
a_MAX
gprof a_MAX.exe → 2.89sec
gcc -pg -o a.exe Eratosthenes.c
a.exe
gprof a.exe → 9.48sec
****/
int main(int argc, char* argv[])
{
unsigned long long int prime_max = 1000000000;
bool *prime;
unsigned long long int i, j;
time_t timer;
clock_t exec_start, exec_end;
/* 計測開始 */
exec_start = clock();
/* 配列の領域を確保 & 初期化 */
prime = (bool *)malloc(sizeof(bool) * (prime_max + 1));
for (i = 0; i <= prime_max; ++i)
prime[i] = true;
/* さて、始めるよ！ */
for (i = 2; i <= prime_max/2 ; ++i){
if (!prime[i])
continue; /* 素数で無いなら次へ */
/* 素数の倍数 (=素数で無い) に false を代入 */
for (j = (i << 1); prime_max >= j; j+=i)
prime[j] = false;
}
/* 計測終了 */
exec_end = clock();
printf("elapsedTime %.4f(sec)\n", (double)(exec_end - exec_start)/CLOCKS_PER_SEC);
for (i = (prime_max - 1) ; i > 0 ; i--){
if(prime[i]){
printf("PRIME MAX: %i\n",i);
break;
}
}
return 0;
}
|
.svg){kind=logo}
.svg){kind=icon}
.svg){kind=logo}
.png){kind=small}
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
