求救
查看原帖
求救
690561
违规用户名690561楼主2022/8/26 17:23

sushu函数是欧拉筛 ss是判断素数的 WA了后4个点 求大佬帮帮我找找问题或给个我通过不了的样例谢谢!

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
long long mm = 1000000;
long long nn, a[1000010], b[1000010], m, sum, ii, jj;
void sushu(long long n) {
	memset(a, 0, sizeof(a));
	for(long long i = 2; i <= n; i++) {
		if(a[i] == 0) {
			a[i] = i;
			b[++m] = i;
		}
		for(long long j = 1; j <= m; j++) {
			if(b[j] > a[i] || b[j] > n / i) {
				jj = 0;
				break;
			}
			a[i * b[j]] = b[j];
		}
	}
}
bool ss(long long nn) {
	while(b[ii] <= nn) {
		if(nn == b[ii]) {
			return true;
		}
		ii++;
	}
	return false;
}
int main() {
	sushu(mm);
	ii = 1;
	while(scanf("%lld", &nn) != EOF) {
		sum = 0;
		if(nn == 1) {
			printf("0");
		} else {
			if(ss(nn)) {
				printf("1");
			} else {
				ii = 1;
				while(nn != 1) {
					while(nn % b[ii] == 0 && nn != 1) {
						nn /= b[ii];
						sum++;
					}
					if(nn == 1) {
						break;
					}
					ii++;
					if(ii > m){
						ii = 1;
					}
				}
				printf("%lld", sum);
			}
		}
		printf("\n");
	}
	return 0;
}
2022/8/26 17:23
加载中...