P1156 质因数个数 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2025年3月22日 22:27

质因数个数题解：

P1156

回复 0 | 赞 5 | 浏览 277

#include <bits/stdc++.h> using namespace std; int main() { long long int n; while (cin >> n) { int c = 0; // 从最小的质数 2 开始尝试，不需要判断i是否为质数。因为从 2 开始除，第一个能整除的数必然是质数。 for (l...

西电机试专家

2025年3月14日 11:19

质因数个数题解：二刷优化代码

P1156

回复 1 | 赞 15 | 浏览 282

#include <bits/stdc++.h> using namespace std; //判断是否为质数 int zhi(int a) { if(a<2) return 0;//小于2的均非质数 int flag=1; for(int i=2;i<=sqrt(a);i++){ if(a%i==0) &nbs...

2025年3月14日 20:00

质因数个数题解：递归竟然没爆

P1156

回复 0 | 赞 1 | 浏览 95

递归写着玩的，用打表优化了一下。结果上传了一下竟然没超时，本来想用set优化一下，但我这老DEV版本太低跑不了。贴出来给大家看一眼得了 #include<bits/stdc++.h> using namespace std; int f[10005] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,...

2025年3月9日 12:41

质因数个数求解：有没有大佬帮我看一下，为什么只有75通过率，超时了

P1156

回复 1 | 赞 15 | 浏览 323

#include <bits/stdc++.h> using namespace std; const int maxn = 1000005; long long f[maxn]; //*******************素数筛选法******************** void func(int a) { for (int i = 2; i <= a; i++) { if (f[i] == 0) { ...

2025年3月7日 23:15

质因数个数题解：递归解法

P1156

回复 0 | 赞 3 | 浏览 152

#include<stdio.h> int Prime(int n){//判定素数 if(n <= 1) return 0;//0和1不是素数 if(n == 2 || n == 3) return 1; if(n % 2 == 0 || n % 3 == 0) return 0; for(int i = 5; i * i <= n; i+=6){ if(n % i == 0 || ...

西电机试专家

2025年2月12日 12:00

质因数个数题解：计算机小白的拙劣题解

P1156

回复 0 | 赞 14 | 浏览 329

#include <bits/stdc++.h> using namespace std; //质因数：质因数就是一个数分解成最基础的质数相乘的形式，这些质数就叫它的质因数 //每个数的质因数分解是唯一的（比如12只能是2×2×3） //思路：判断一个数是不是素数，即用它除以小于其根号的数[2-sqrt(i)]，若能整除则说明非素数 //若一个数既是素数，又能被n整除，说明其为素因数 int issu(int a) {//判断一个数是否为素数 for(int i=2;i&l...

今夕何夕12211

2024年3月26日 10:39

质因数个数题解：

P1156

回复 1 | 赞 8 | 浏览 830

q求助显示超时准确率只有75% #include <stdio.h> #include <stdlib.h> #include <string.h> int isprime(int n) { int sqt=sqrt(n); if(n==1) return 0; if(n==2) return 1; f...

2024年5月8日 23:55

质因数个数(数论)题解：

P1156

回复 0 | 赞 9 | 浏览 702

#include<bits/stdc++.h> using namespace std; int n; int divide(int n) { int cnt = 0; for(int i = 2; i <= n / i; i ++) { if(n % i == 0) { while(n % i == 0) n /= i, cnt ++; } } if(n > 1) cnt ++; ...

2023年3月21日 15:43

质因数个数

P1156

回复 1 | 赞 23 | 浏览 2.6k

注意这几点: 1.判断质数判断到sqrt就行,这样可以节省一半时间; 2.为了解决有多个重复因数的情况,每次都让i=2. #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<math.h> int main() { int n; while (scanf("%d", &n) != EOF) { int i = 2; int step = 0; while (n > 1) { if (n % i == 0) {...

2024年3月21日 20:32

质因数个数题解：

P1156

回复 0 | 赞 1 | 浏览 809

#include <stdio.h> #include <cstring> #include <iostream> using namespace std; const int maxn = 1000000 + 5; int prime[maxn]; void getprime(){ memset(prime,0,sizeof(prime)); for(int i = 2;i <=maxn;i++){ &...

1
2
3

题目质因数个数

题解数量27

发布题解在线答疑

热门题解

1 质因数个数

2 质因数个数题解：二刷优化代码

3 质因数个数求解：有没有大佬帮我看一下，为什么只有75通过率，超时了

4 质因数个数题解：计算机小白的拙劣题解

5 质因数个数题解：简短的解

6 [c]看了其它人的算法，我觉得有一个思想需要告诉大家。

7 质因数个数(数论)题解：

8 质因数个数题解：

9 质因数个数题解：

10 75%的原因：如果本身是质数就要单独处理，否则就会超时