一、最大公约数
- 题目描述
输入两个正整数，求其最大公约数。
- 输入描述
测试数据有多组，每组输入两个正整数。
- 输出描述
对于每组输入,请输出其最大公约数。
- 示例输入
49 14
- 示例输出
7
解题思路
a、b的最大公约数同时也是b、a mod b的最大公约数。转化为求b、a mod b的最大公约数，问题不变而数据规模明显变小。不断重复此过程，直到问题缩小成求某个非0数与0的最大公约数，则该非0数即是所求。
欧几里得算法：
(1)若a、b全为零，则最大公约数不存在；
(2)若a、b其中之一为零，则最大公约数为非零的那个；
(3)若a、b都不为零，则使新a=b；新b=a%b然后重复该过程。
代码9.1
#include <stdio.h>
int gcd(int a, int b){
if(b == 0)
return a;
else
return gcd(b, a % b);
}
int main()
{
int a, b;
while(scanf("%d%d",&a, &b) != EOF)
{
printf("%d\n",gcd(a, b));
//若求最小公倍数，a*b/最大公约数 即可
//printf("%d\n",a * b / gcd(a, b);
}
}
二、素数判定
- 题目描述
给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。
- 输入描述
测试数据有多组，每组输入一个数n。
- 输出描述
对于每组输入,若是素数则输出yes，否则输入no。
- 示例输入
13
- 示例输出
yes
解题思路
素数即只能被自身和1整除的大于1的正整数，只需要测试位于区间[2,sqrt(n))之间的正整数是否均不能整除n，若均不能整除n，则判定n为素数。
代码9.2
#include <stdio.h>
#include <math.h>
bool judge(int n)
{
if(n <= 1) return false;
int bound = (int)sqrt(n) + 1; //枚举上界，为防止double值带来的精度损失，根号取整后多+1
for(int i = 2; i < bound; i++){
if(n % i == 0) return false;
}
return true;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
if(judge(n) == true)
printf("yes\n");
else
printf("no\n");
}
}
三、素数筛法
- 题目描述
输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。
- 输入描述
输入有多组数据。每组一行，输入n。
- 输出描述
输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。
- 示例输入
100
- 示例输出
11 31 41 61 71
解题思路
素数筛法：从2开始遍历2到10000的所有整数，若当前整数没有被标记成非素数，则判定为素数，并将其所有倍数标记为非素数。继续遍历下一个数，直到遍历完。此时所有没被标记成非素数的数即为筛选出来的素数。
代码9.3
#include <stdio.h>
int prime[10000]; //保存筛得的素数
int primeSize = 0; //保存的素数个数
bool mark[10001]; //mark[x]为true，表示x被标记为非素数
void init() //素数筛法
{
for( int i = 1; i <= 10000; i++)//初始化，所有数字均为被标记
{
mark[i] = false;
}
for(int i = 2; i <= 10000; i++)
{
if(mark[i] == true )continue; //若该数字已被标记为非素数，跳过
prime[primeSize++] = i; //否则为素数
for( int j = i*i; j <= 10000; j +=i)//并将该素数的所有倍数标记为非素数
{
mark[j] = true;
}
}
}
int main(){
init(); //素数筛法，保存2-10000之间的所有素数
int n;
while(scanf("%d", &n) != EOF)
{
bool isOutput = false;
for(int i = 0; i < primeSize; i++)
{
if(prime[i] < n && prime[i] % 10 == 1)
{
if(isOutput == false){//第一个输出的素数，之前不需要加空格
printf("%d", prime[i]);
isOutput = true;
}
else{
printf(" %d",prime[i]);//输出前加空格
}
}
}
if(isOutput == false)//不存在符合条件的素数
{
printf("-1\n");
}
else printf("\n");
}
return 0;
}
