[Pythonプログラミング]いろんな方法で素数を求めてみるよ | 関連情報素数 を 求める プログラム新しい更新をカバーします

One thought on “[Pythonプログラミング]いろんな方法で素数を求めてみるよ | 関連情報素数 を 求める プログラム新しい更新をカバーします”

1. 

   kjsaka says:

   1ヶ月少し前にメルセンヌ素数をリュカ・レーマー・テストで発見するC言語プログラムを作ったので載せます。
   当時,他の動画へのコメント用に1日で作った物なので,19728桁以下の制限付ですし,改善の余地も多数あるとは思いますが…
   同じ計算をする式(n<<4 等)が複数箇所に出て来ますが、これはコンパイラによる最適化をあてにしているからです。
   #include <stdio.h>
   #define Size 4096
   typedef unsigned int uint;
   int test(int p);
   uint s[Size], ss[Size<<1];
   int main(int argc, char* argv[]){
   int a,p;
   for (p = 3; p < (Size<<4); p += 2){
   a = 3; while (a*a <= p && (p % a) != 0){ a += 2; }
   if (a*a > p && test(p)){ printf("2^%d-1n", p); }
   }
   return 0;
   }
   int test(int p){
   int L,idx,m,n,i,j,k;
   uint r,b;
   L = ((p-1)>>4)+1;
   s[0] = 4; for (m = 1; m < L; m++){ s[m] = 0; }
   for (idx = 2; idx < p; idx++){
   for (m = 0; m < L+L; m++){ ss[m] = 0; }
   for (m = 0; m < L; m++){
   r = 0;
   for (n = m; n < m+L; n++){
   r = r + ss[n] + s[m] * s[n-m]; ss[n] = (r & 0xFFFF); r >>= 16;
   }
   while (r != 0){
   r += ss[n]; ss[n] = (r & 0xFFFF); r >>= 16; n++;
   }
   }
   r = ss[0] – 2; ss[0] = (r & 0xFFFF); r >>= 16;
   m = 1; n = ((p+p-1)>>4);
   while (r != 0 && m <= n){ r = ss[m] – 1; ss[m] = (r & 0xFFFF); r >>= 16; m++; }
   if (r != 0){
   ss[0] = ((ss[0] – 1) & 0xFFFF);
   m = (p>>4); ss[m] = ((ss[m] + (1<<(p & 0xF))) & 0xFFFF); m++;
   while (m <= n){ ss[m] = 0; m++; }
   }
   for (i = p-1; i >= 0; i–){
   b = 0;
   for (n = ((i+p)>>4); n >= (i>>4); n–){
   j = i -(n<<4); if (j < 0){ j = 0; }
   k = i+p-(n<<4); if (k > 16){ k = 16; }
   if (k <= j){ r = 0; } else { r = (((1<<(k-j))-1)<<j); }
   if (r != ss[n]){
   if (r > ss[n]){ b = 1; }
   break;
   }
   }
   if (b == 0){
   for (n = (i>>4); n <= (((i+p)-1)>>4); n++){
   j = i -(n<<4); if (j < 0){ j = 0; }
   k = i+p-(n<<4); if (k > 16){ k = 16; }
   r = ss[n] – b – (((1<<(k-j))-1)<<j);
   ss[n] = (r & 0xFFFF); b = ((r>>16) & 1);
   }
   while (b != 0 && n <= (((p-1)+p)>>4)){
   r = ss[n] – b; ss[n] = (r & 0xFFFF); b = ((r>>16) & 1); n++;
   }
   }
   }
   for (m = 0; m < L; m++){ s[m] = ss[m]; }
   }
   for (m = 0; m < L; m++){ if (s[m] != 0){ return 0; } }
   return 1;
   }

   27/11/2022 at 6:24 PM

   返信