試除法判定質數
題目描述
給定n個正整數ai，判定每個數是否是質數。
輸入格式
第一行包含整數n。
接下來n行，每行包含一個正整數ai。
輸出格式
共n行，其中第 i 行輸出第 i 個正整數ai是否為質數，是則輸出“Yes”，否則輸出“No”。
數據范圍
1≤n≤100,
1≤ai≤2?109
輸入樣例：
2
2
6
輸出樣例：
Yes
No
代碼
#include<iostream>
using namespace std;bool is_prime(int x)
{if(x<2) return false;for(int i=2;i<=x/i;++i){if(x%i == 0)return false;}return true;
}
int main()
{int n;cin>>n;int x;while(n--){cin>>x;if(is_prime(x)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
分解質因數
題目描述
給定n個正整數ai，將每個數分解質因數，并按照質因數從小到大的順序輸出每個質因數的底數和指數。
輸入格式
第一行包含整數n。
接下來n行，每行包含一個正整數ai。
輸出格式
對于每個正整數ai,按照從小到大的順序輸出其分解質因數后，每個質因數的底數和指數，每個底數和指數占一行。
每個正整數的質因數全部輸出完畢后，輸出一個空行。
數據范圍
1≤n≤100,
1≤ai≤2?109
輸入樣例：
2
6
8
輸出樣例：
2 1
3 12 3
代碼
#include<iostream>
using namespace std;void divide(int x)
{for(int i=2;i<=x/i;++i){if(x%i == 0){int s = 0;while(x%i == 0){x/=i;s++;}printf("%d %d\n",i,s);}}if(x>1) printf("%d %d\n",x,1);cout<<endl;
}int main()
{int n,x;cin>>n;while(n--){cin>>x;divide(x);}return 0;
}
篩質數
題目描述
給定一個正整數n，請你求出1~n中質數的個數。
輸入格式
共一行，包含整數n。
輸出格式
共一行，包含一個整數，表示1~n中質數的個數。
數據范圍
1≤n≤106
輸入樣例：
8
輸出樣例：
4
樸素篩法
#include<iostream>
using namespace std;const int N =1000010;
bool st[N];
int primes[N],cnt;void is_prime(int n)
{for(int i=2;i<=n;++i){if(st[i]) continue;primes[cnt++] = i;for(int j = i+i;j<=n;j+=i){st[j] = true;}}
}
int main()
{int n;cin>>n;is_prime(n);cout<<cnt<<endl;return 0;
}
線性篩法
#include<iostream>
using namespace std;const int N =1000010;
bool st[N];
int primes[N],cnt;void is_prime(int n)
{for(int i=2;i<=n;++i){if(!st[i]) primes[cnt++] = i;for(int j=0;primes[j]<=n/i;++j){st[primes[j]*i] = true;if(i % primes[j] == 0) break;}}
}
int main()
{int n;cin>>n;is_prime(n);cout<<cnt<<endl;return 0;
}
