素数及最大公约数求解

标题素数判断

#include<stdio.h> int main() { int i, m; scanf("%d", &m); int flag = 1; // 标志 for(i = 2; i < m; i++){ if(m % i == 0){ // 判断非质数更加简单 flag = 0; // 更新标志 break; } } if(flag == 1){ printf("%d is prime.", m); } else{ printf("%d is not prime.", m); } return 0; }

标题素数打印

#include<stdio.h> #include<stdlib.h> #include<math.h> int main() { int i,j,x,k,n; scanf("%d", &j); for(x = 2; x < j; x++){ k = sqrt(x); // 根号x的右边出现约数，其左边必定有对应的约数。 for(i=2 ; i <= k; i++){ // 减少循环次数 if(x % i == 0){ break; } } if(i == k+1){ printf("%d\t", x); n++; if(n % 8 == 0){ // //8个一行输出 printf("\n"); } } } return 0; }

辗转相除法求最大公约数:

原理：两个整数的最大公约数等于其中最小的数和两数的相除余数的最大公约数。 1.如果b==0，计算结束，a就是最大公约数。 2.否则计算a%b，a=b，b=a%b。 3.重复第一步。

// 辗转相除法求最大公约数 #include<stdio.h> int main() { int a, b, r; //r表示余数 printf("输入两个整数:"); scanf("%d %d", &a, &b); while(b != 0) { r = a % b ; a = b; b = r; } printf("最大公约数 = %d\n", a); return 0; }