|
|
ミラーラビン素数判定法を追加しました。
OPTION CHARACTER BYTE
LET NUM=10
FOR I=2 TO 1000
LET N$=STR$(I)
PRINT I;":";
LET L=ISPRIME2(N$,NUM)
SELECT CASE L
CASE 0
PRINT "合成数"
CASE 1
PRINT "確率的素数"
CASE 2
PRINT "確定的素数"
END SELECT
NEXT I
END
EXTERNAL FUNCTION ISPRIME2(N$,NUM)
OPTION CHARACTER BYTE
ASSIGN ".\DLL\isprime2.dll","isprime"
END FUNCTION
------------------------------------------------------------------------------------
isprime2.cpp
#include <mpirxx.h>
#pragma comment(lib, "mpir.lib")
using namespace std;
mpz_class atompz(char *str)
{
mpz_class result = 0;
while (*str>='0' && *str<='9') {
result=(result*10)+(*str++ - '0');
}
return result;
}
extern "C" __declspec(dllexport) int isprime(char *x,int num)
{
int m;
mpz_class n;
n=atompz(x);
m=mpz_probab_prime_p(n.get_mpz_t(), num); // convert mpz_class to mpz_t
return m;
}
有理数モードで「色々」な素数を求めてみました。
!'メルセンヌ素数(2^n-1)
!'n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941
!'階乗素数(n! + 1)
!'n = 1 2 3 11 27 37 41 73 77 116 154 320 340 399 427 872
!'階乗素数(n! - 1)
!'n = 3 4 6 7 12 14 30 32 33 38 94 166 324 379 469 546
OPTION CHARACTER BYTE
OPTION ARITHMETIC RATIONAL
FOR I=2 TO 1000
!' LET A$=STR$(3^I-2) !' 2 4 5 6 9 22 37 41 90 102 105 317 520 541 561 648 780 786 957 1353 2224 2521
!' LET A$=STR$(5^I-2) !' 2 14 26 50 126 144 260 624
!' LET A$=STR$(5^I-4) !' 5 7 15 47 81 115 267 285
LET A$=STR$(2^I-1) !' 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941
!' LET A$=STR$(7^I-2) !' 1 2 4 7 8 12 15 28 31 84 98 128 238 302 859 1508 1586 2091
!' LET A$=STR$(7^I-6) !' 2 3 6 9 21 25 33 49 54 133 245 255 318
!' LET A$=STR$(11^I-4) !' 1 3 5 21 119 891
IF ISPRIME2(A$,50)>0 THEN PRINT I;LEN(A$);"桁"
NEXT I
END
EXTERNAL FUNCTION ISPRIME2(N$,NUM)
OPTION CHARACTER BYTE
OPTION ARITHMETIC RATIONAL
ASSIGN ".\DLL\isprime2.dll","isprime"
END FUNCTION
なお、実行時には mpir.dllが別途必要です。(isprime.dllを除く (ISPRIMEDLL.BAS))
前頁の「多倍長計算」と合わせて一緒にダウンロードしてください。
下記からダウンロードしてください。
●BASICAcc(win64) x64版 (miller-rabin(x64).zip)
https://37.gigafile.nu/0315-ce6a5364e26e6e83196ce0dea4186b222
ダウンロード期限：2020年3月15日(日)
ダウンロードパスワード：未設定
●BASIC(win32) x86版 (miller-rabin(x86).zip)
https://37.gigafile.nu/0315-c9a355280d5fb4c52e48c947e7209da16
ダウンロード期限：2020年3月15日(日)
ダウンロードパスワード：未設定
|
|