王道机试指南6.2素数6.3分解质因数
例题6.7素数判定(哈尔滨工业大学上机)
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n, flag = 0;
while(cin >> n){
if(n == 1 || n == 0 || n < 0){
flag =1;
}
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
flag = 1;
break;
}
}
if(flag == 1) cout << "no" << endl;
else cout << "yes" << endl;
}
return 0;
}
例题6.8素数(北京航空航天大学上机)
#include<iostream>
#include<cstdio>
using namespace std;
int flag[10001] = {0};
int main(){
int n;
while(cin >> n){
for(int i = 2; i <= n; i++){
if(flag[i] == 0){
for(int j = 2; j * i <= n; j++){
flag[i * j] = 1;
}
}
}
int space = 0;
int none = 0;
for(int i = 2; i <= n; i++){
if(i % 10 == 1 && flag[i] == 0){
if(space == 1){
cout << " " ;
}
cout << i;
space = 1;
none = 1;
}
}
if(none == 0) cout << -1;
}
return 0;
}
例题6.9质因数个数(清华大学复试上机)
下面的代码本地通过了,但是没有AC提示段错误,不调用函数不显示段错误,应该是调用层数太多了,需要重构
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int flag[1000] = {0};
vector<int> v;
void primnum(int n){
for(int i = 2; i * i <= n; i++){
if(flag[i] == 0){
for(int j = 2; j * i <= n; j++){
flag[j * i] = 1;
}
}
}
for(int i = 2; i < n; i++){
if(flag[i] == 0){
v.push_back(i);
}
}
}
int main(){
int n;
while(cin >> n){
int sum = 0;
v.clear();
primnum(n);
for(int i = 0; i < v.size(); i++){
while(n % v[i] == 0){
n /= v[i];
sum++;
}
}
cout << sum << endl;
}
return 0;
}
参考了别人代码后,进行了重构
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main(){
int n;
while(cin >> n){
int sum = 0;
for(int i = 2; i * i< n; i++){
while(n % i == 0){
n /= i;
sum++;
}
}
if(n > 1) sum++;//
cout << sum << endl;
}
return 0;
}
习题6.7约数个数(清华大学复试上机)
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
int n;
while(scanf("%d",&n) != EOF){
for(int i = 0; i < n; i++){
int temp, count = 0;
scanf("%d", &temp);
int bound = (int)sqrt((double)temp) + 1;
for(int j = 1; j <= bound; j++){
if(temp % j == 0){
count++;
if(temp / j > bound) count++;
}
}
printf("%d\n", count);
}
n--;
}
return 0;
}