素数检测、因式分解CSU 1030 素数槽
目录
一，素数检测
素数检测就是给定一个正整数n，判断其是不是素数。
最简单方案：
枚举不超过sqrt(n)的所有素数，判断有没有n的因子。
-
bool isPrime(int n)
-
{
-
if (n == 2)return true;
-
if (n % 2 == 0)return false;
-
for (int i = 3; i*i <= n; i += 2) if (n%i == 0)return false;
-
return true;
-
}
CSU 1030 素数槽
题目：
Description
处于相邻的两个素数p和p + n之间的n - 1个连续的合数所组成的序列我们将其称为长度为n的素数槽。例如，‹24, 25, 26, 27, 28›是处于素数23和素数29之间的一个长度为6的素数槽。
你的任务就是写一个程序来计算包含整数k的素数槽的长度。如果k本身就是素数，那么认为包含k的素数槽的长度为0。
Input
第一行是一个数字n，表示需要测试的数据的个数。后面有n行，每行是一个正整数k， k大于1并且小于或等于的第十万个素数（也就是1299709）。
Output
对于输入部分输入的每一个k，都对应输出一个非负整数，表示包含k的素数槽的长度，每个非负整数占一行。
Sample Input
5
10
11
27
2
492170
Sample Output
4
0
6
0
114
代码：
-
#include<iostream>
-
#include<stdio.h>
-
using namespace std;
-
-
bool isPrime(int n)
-
{
-
if (n == 2)return true;
-
if (n % 2 == 0)return false;
-
for (int i = 3; i*i <= n; i += 2) if (n%i == 0)return false;
-
return true;
-
}
-
-
int main()
-
{
-
int t;
-
scanf("%d", &t);
-
int n;
-
while (t--)
-
{
-
scanf("%d", &n);
-
int l = 0;
-
for (int i = 0; !isPrime(n + i); i++) l++;
-
for (int i = 0; !isPrime(n - i); i++) l++;
-
printf("%d\n", l);
-
}
-
return 0;
-
}
这个比较暴力，比较慢，404ms
更快的方法是预处理存下所有素数，同时存下每个数在哪2个素数之间
代码：
-
#include<iostream>
-
#include<stdio.h>
-
using namespace std;
-
-
int list[1299710], p[100001];
-
-
int main()
-
{
-
int key = 0, t, n;
-
for (int i = 0; i < 1299710; i++)list[i] = i % 2;
-
p[0] = 2, list[1] = 0, list[2] = 1;
-
for (int i = 3; i < 1299710; i += 2)if (list[i])
-
{
-
p[++key] = i;
-
for (int j = i + i; j < 1299710; j += i)list[j] = 0;
-
}
-
for (int i = 3; i < 1299710; i++)list[i] += list[i - 1];
-
scanf("%d", &t);
-
while (t--)
-
{
-
scanf("%d", &n);
-
printf("%d\n", p[list[n - 1]] - p[list[n] - 1]);
-
}
-
return 0;
-
}
这样就很快，52ms
CSU 2051: Num
题目：
Description
编一程序，输入正整数N（N在2～32767之间）， 求它的最大质因子（包括它本身）。
Input
只有一行，就是正整数N
Output
所求的最大质因子
Sample Input
7
Sample Output
7
代码：
-
#include<iostream>
-
using namespace std;
-
-
bool prime(int n)
-
{
-
if (n % 2 == 0)return n == 2;
-
for (int i = 3; i*i <= n; i += 2)if (n%i==0)return false;
-
return true;
-
}
-
-
int main()
-
{
-
int n;
-
cin >> n;
-
for (int i = n;; i--)if (prime(i) && n%i == 0)
-
{
-
cout << i;
-
break;
-
}
-
return 0;
-
}
二，因式分解
CSU 1522: Extravagant number
题目：
Description
An extravagant number (also known as a wasteful number) is a natural number which has fewer digits than the number of digits in its prime factorization (including exponents).For example, in base-10 arithmetic 4 = 2², 6 = 2 × 3, 8 = 2³, and 9 = 3² are extravagant numbers. Extravagant numbers can be defined in any base. There are infinitely many extravagant numbers, no matter what base is used.
----according to wikipedia.
Your task is to judge whether an integer (in base-10) is an extravagant number or not.
Input
There are several test cases.
First line of the input is the an integer T which means the number of test cases. Then Tlines follow, each line contains an integer n (n<=1000000).
Output
For each test case, you should output one line. If the number is an extravagant number, you should output “Yes”. Otherwise, “No”.
Sample Input
3
4
256
125
Sample Output
Yes
No
No
这个题目完全没什么技巧，直接求出因式分解，然后用一个函数num求出任意整数m有多少位。
要说唯一的技巧，那就是不需要任何数组。
代码：
-
#include<iostream>
-
using namespace std;
-
-
bool prime(int m)
-
{
-
for (int i = 2; i*i <= m; i++)if (m%i == 0)return false;
-
return true;
-
}
-
-
int num(int m)
-
{
-
if (m == 1)return 0;
-
int s = 0;
-
while (m)
-
{
-
s++;
-
m /= 10;
-
}
-
return s;
-
}
-
-
int main()
-
{
-
int t;
-
int n, k, sum;
-
cin >> t;
-
for (int cas = 1; cas <= t; cas++)
-
{
-
cin >> n;
-
sum = num(n);
-
for (int i = 2; i <= n; i++)
-
{
-
if (i + i > n)i = n;
-
if (prime(i) && n%i == 0)
-
{
-
k = 0;
-
while (n%i == 0)
-
{
-
k++;
-
n /= i;
-
}
-
sum -= num(i)+num(k);
-
}
-
}
-
if (sum < 0)cout << "Yes";
-
else cout << "No";
-
cout << endl;
-
}
-
return 0;
-
}
CodeForces - 27E 谁有N个因数？
题目：
Description
Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n the answer will not exceed 1018.
Input
The first line of the input contains integer n (1 ≤ n ≤ 1000).
Output
Output the smallest positive integer with exactly n divisors.
Sample Input
Input
4
Output
6
Input
6
Output
12
这个题目，我最大的失败就在于，考虑了很多不必要的细节。
不过反正比赛也结束了，现在终于也AC了，还是写一下吧。
首先，结果肯定只会出现2^a * 3^b * 5^c * 7^d * 11^e * 13^f ^ 15^g这种形式的数，其中a,b,c,d,e,f,g都是非负整数。
其次，a,b,c,d,e,f,g肯定是单调不增的。
于是可以进行一系列的估值（我好无聊）
得到，g<2,f<3,e<3,d<5,c<7,b要么不超过6，要么是某个素数-1,a要么是不超过8，要么是某个素数-1
而且，b本身不超过35，a本身不超过59。
于是还专门写了一个判断是不是10到60之间的素数的函数。
光是这几个取值范围，结果也就只有十几万种情况，如果再考虑单调性，应该只有几千种而已。
不过，这实在太细致了，没什么卵用。
代码：
-
#include<iostream>
-
using namespace std;
-
-
bool is_prime(int n) //10到60的素数
-
{
-
if (n == 11 || n == 13 || n == 17 || n == 19 || n == 23 || n == 29 || n == 31 || n == 37)return true;
-
if (n == 41 || n == 43 || n == 47 || n == 53 || n == 59)return true;
-
return false;
-
}
-
-
int main()
-
{
-
int n;
-
while (cin >> n)
-
{
-
long long min = 1000000000000000000;
-
int m1 = n;
-
for (int i17 = 0; i17 < 2; i17++)
-
{
-
if (m1 % (i17 + 1))continue;
-
int m2 = m1 / (i17 + 1);
-
for (int i13 = i17; i13 < 3; i13++)
-
{
-
if (m2 % (i13 + 1))continue;
-
int m3 = m2 / (i13 + 1);
-
for (int i11 = i13; i11 < 3; i11++)
-
{
-
if (m3 % (i11 + 1))continue;
-
int m4 = m3 / (i11 + 1);
-
for (int i7 = i11; i7 < 5; i7++)
-
{
-
if (m4 % (i7 + 1))continue;
-
int m5 = m4 / (i7 + 1);
-
for (int i5 = i7; i5 < 7; i5++)
-
{
-
if (m5 % (i5 + 1))continue;
-
int m6 = m5 / (i5 + 1);
-
for (int i3 = i5; i3 < 31; i3++)
-
{
-
if (i3>6 && !is_prime(i3 + 1))continue;
-
if (m6 % (i3 + 1))continue;
-
int i2 = m6 / (i3 + 1) - 1;
-
if (i2 <i3)continue;
-
if (i2>8 && !is_prime(i2 + 1))continue;
-
long long s = 1;
-
for (int i = 0; i < i17; i++)s *= 17;
-
for (int i = 0; i < i13; i++)s *= 13;
-
for (int i = 0; i < i11; i++)s *= 11;
-
for (int i = 0; i < i7; i++)s *= 7;
-
for (int i = 0; i < i5; i++)s *= 5;
-
for (int i = 0; i < i3; i++)
-
{
-
s *= 3;
-
if (s < 0)break;
-
}
-
if (s < 0)continue;
-
for (int i = 0; i < i2; i++)
-
{
-
s *= 2;
-
if (s < 0)break;
-
}
-
if (s<0)continue;
-
if (min>s)min = s;
-
}
-
}
-
}
-
}
-
}
-
}
-
cout << min;
-
cout << endl;
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/115611101
- 点赞
- 收藏
- 关注作者
评论（0）