关于质数

关于质数

质数是只能被1或者自身整除的自然数(不包括1),称为质数。

判断是质数还是合数

1,初级

int n, i;
scanf("%d", &n);
for (i = 2; i <= n; i ++)//将所有可能的因子都遍历一遍
	if (i == n) printf("prime number");//根据因子是否会达到它本身来判断它是否为质数
	else if (n%i == 0)
	{
     
		printf("conposite number");
		break; 
	}

2,改进

//如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。

3,计数法

	int i, n, count = 0;
	scanf("%d", &n);
	if(n >= 2)
	{
     
		for (i = 1; i <= n; i++)
        	if (n % i == 0) count++; // 统计能够整除自己的个数
    	if (count == 2)     // 只有1和自己两个数可以整除自己,则为质数
        	printf("prime number");
    	else
        	printf("conposite number");
	}
    else printf("error!");

取出质数

	//输出某个范围中的质数
	int n, i, count;
	for(n = 2; n < 1000; n ++)
	{
     
		for(i = 2; i <= n; i ++)
		{
     
			if(i == n)
			{
     
				count ++;
				printf("%d ", i);
				break;
			}
			if(n%i == 0)break;	
		}	
	}
	printf("%d", count);
//取出某个范围内的质数
#include 
#include 
int main() 
{
     
//先将数组元素与数值相对应,若该数为合数,则对应的数组元素为0;若为质数,则对应的数组元素为1。最后根据数组元素是0还是1来输出质数 
    int i, j, n;
    int num = 100;  //1-100之内的质数,如果求1-10000之间的质数,则num=10000
    int a[101];     //因为数组下标是从0开始,为使下标和数一一对应,让数组多定义一个元素
    for (i = 0; i <= 101; i ++) a[i] = i;   /*初始化数组*/
    a[1] = 0;   //1不是质数,令a[1]为0 
    for (i = 2; i < sqrt(num); i ++) //所有可能存在的质因数 
	{
     
        for (j = i + 1; j <= num; j ++) 
            if (a[j] != 0 && a[j]%i == 0) a[j] = 0;    /*如果是质数了,则不需要再判断;a[j]不是质数,则a[j]=0*/
        /*依次判断是不是2的倍数,3的倍数,4的倍数。。。。。。。。*/
    } 
    for(i = 1, n = 0; i <= 100; i++) 
        if (a[i] != 0) 
		{
     
            printf("%d\t", a[i]);/*输出a[i]不为0的数(即质数)*/
            if(++n%10 == 0) printf("\n");//(换行,妙!!!) 
        }
    return 0;
}
	//3位数中的回文质数
	int n,i,count=0;
	for(n=100;n<1000;n++)
		if((n/100) == (n%10))//回文数判断 
			for(i=2;i<=n;i++)//将可能的因子从2开始遍历 
			{
     
				if(i==n)//质数判断 
				{
     
					printf("%d ",i);
					count++;
					if(count%4==0)printf("\n"); //输出4个后换行 
					break;
				}
				if(n%i==0)break; //合数 
			}
	printf("\n%d",count);

分解质因数

#include
int main()
{
     
	int n,i;
	printf("请输入一个数:");
	scanf("%d",&n);
	printf("%d=",n);
	for(i=2;i<=n;i++)//因子直接从2开始考虑 
	{
     
		while(i!=n) //把所有小于n的数拿来,看能否作为因子 
		{
     
			if(n%i==0)//该数可以作为因子的情况,也即n为合数 
			{
     
				printf("%d*",i);//输出一个因子 
				n=n/i;//原数除去这个因子 
			}         //检查有无重复的因子,将重复的因子输出 
			else break; /*1,若该数i不能作为因子,则取下一个整数;
			              2,n不再有重复的因子i时;取下一个整数*/ 
		}/*在for循环里嵌套一个while循环,目的便在于输出重复的因子:
		   其中包含了一个i能否再作为n/i的因子的重复判断,操作。
		    不能再作为因子时,用break只跳出while循环 */
	} 
	 printf("%d",n);/*由于输入因子时为从小到大按顺序进行判断的,所以n不断地除去因子之后,最终必然成为了它最大的因子(质数)
	                 此时再输入因子,已不再满足i!=n的循环条件,因此需要单独输出n(即原数的最大因子)*/ 
	 return 0;
 } 

你可能感兴趣的