问题 1234: 检查一个数是否为质数/素数【新思路】

以往的思路，不存在BUG

以往判断一个数n都是进行一个个枚举，看从2开始的数中是否整除n，这样做的时间复杂度为O(n)，并不是最优解哦~
代码如下：

#include<stdio.h>
int main()
{
	int n,i,sign;
	while(~scanf("%d", &n)){
		for(sign=1,i=2;i<=n/2&&sign;i++){
			if(n%prime[i]==0)	sign=0;
		}
		if(n!=1&&sign)	printf("Y\n");
		else	printf("N\n");
	}
	return 0;
}

新思路，利用质数/素数【BUG】

今天在写另一道题目的时候想出来一个求解一个数的约数的种类的方法时，突然想到下面这种方法
将10以内的素数：2、3、5、7放入一个数组中，然后将n依次除以每一个数，如果能够整除，则不是素数
为什么要以十以内的素数为标准？
任何一个非素数都是有相应的约数，可以通过观察得到约数全部为质数
注意：排除n=1的情况，毕竟1不是素数
BUG：需要不断地计算质数
时间复杂度：O(1)
代码如下：

#include<stdio.h>
int prime[4] = {2,3,5,7};
int main()
{
	int n,i,sign;
	while(~scanf("%d", &n)){
		for(sign=1,i=0;i<4&&sign;i++){
			if(n==prime[i])	break;
			else if(n%prime[i]==0)	sign=0;
		}
		if(n!=1&&sign)	printf("Y\n");
		else	printf("N\n");
	}
	return 0;
}

图片镇帖
代码极其无聊，不能颓~~~~