Description
給你很多的正整數，只是為了找出有多少素數，
Input
有很多的測驗用例，每個測驗用例第一行是正整數N，表示要從N個整數中找，每個整數不超過2147483647，其中每個不小于2，
Output
對于每種情況輸出素數的個數，
Sample Input
3
2 3 4
Sample Output
2
**
利用米勒羅賓法判斷素數
不知道其他篩選方法能不能過，
線性篩模板鏈接https://blog.csdn.net/qq_33969563/article/details/109277853
**
米勒羅賓模板
原理不太懂啊，暫時只會套用
int tab[]={2, 3, 5, 7};
long long qpow(int a, int b, int r) //(a^b)%r 快速冪取模
{
long long ret = 1, tmp = a;
while(b)
{
if (b&1)
ret = ret*tmp%r;
tmp = tmp*tmp%r;
b >>= 1;
}
return ret;
}
bool Miller_Rabbin(int n, int a)//米勒拉賓素數測驗
{
int r = 0, s = n-1, j;
long long k;
if(n%a == 0) return false;
while((s&1) == 0)
{
s >>= 1;
r++;
}
k = qpow(a, s, n);
if(k == 1) return true;
for (j = 0; j < r; j++, k=k*k%n)
if (k == n-1)
return true;
return false;
}
bool Isprime(int n)//判斷是否是素數，如果是回傳1
{
for (int i = 0; i < 4; i++)
{
if (n == tab[i])
return true;
if (!Miller_Rabbin(n, tab[i]))
return false;
}
return true;
}
主函式部分
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
int ar[1000000]；
/******************這里寫上面的米勒羅賓模板******************/
int main()
{
int n, sum;
while(scanf("%d",&n)!=EOF)//多組測驗樣例
{
sum = 0;//注意sum要清零，因為這個wa了一次，艸
for(int i = 1 ; i <= n; i++)
{
scanf("%d",&ar[i]);
bool k = 0;/*利用bool型變數k的值判斷是否為素數，一開始將其賦為0(0表示不是素數，1表示是素數）*/
k = Isprime(ar[i]);//呼叫這個函式
if(k)
sum++;
}
printf("%d\n",sum);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/198343.html
標籤：python