11-对求素数的研究和分析

短命女 2022-12-21 04:53 104阅读 0赞

> 筛选法又称筛法，具体做法是:先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做"埃拉托斯特尼筛"，简称"筛法"。(另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。)

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    //常见错误的写法
    void  Sushu1()
    {
        
    	int j;
    	for(int i=9;i<120;i++)
    	{
        	for(j=2;j<i;j++)
    		{
        
    		
    			if(i%j == 0)//不是素数
    			{
        
    				printf("%d不是素数\n",i);
    			}
    			else
    			{
        
    				printf("%d是素数\n",i);
    			}
    		}
    	}
    }
    
    //输出100到200之间的素数的正确做法  
    void Sushu2()
    {
        
    	int j;
    	for(int i=100;i<200;i++)
    	{
        
    		for(j=2;j<i;j++)
    		{
        
    			if(i%j == 0)//不是素数
    			{
        
    				break; // 跳出一层循环
    			}
    		}
    		if(j == i)//是素数
    		{
        
    			printf("%d\n",i);
    		}
    	}
    }
    //利用筛选法求n以内的素数,素数直接输出,方法1 
    void Primer1(int n)
    {
        
    	int *arr = (int *)malloc(n*sizeof(int));//创建n个标记
    	//int  arr[n];//error
    	int i;
    	for(i=0;i<n;i++)//用1表达是素数,0表达不是素数
    	{
        
    		arr[i] = 1;
    	}
    
    	arr[0] = arr[1] = 0;//0,1不参与
    	for(i=2;i<n;i++)
    	{
        
    		for(int j=i+1;j<n;j++)//遍历i后面所有的元素,判断是否为i的倍数,如果是则不是素数
    		{
        
    			if(j%i == 0)//j不是素数
    			{
        
    				arr[j] = 0;
    			}
    		}
    	}
    
    	for(i=0;i<n;i++)
    	{
        
    		if(arr[i] == 1)
    		{
        
    			printf("%d \n",i);
    		}
    	}
    	free(arr);
    }
    
    //方法2，将所有的素数返回
    int * Primer(int n,int *rtlen)
    {
        
    	int *arr = (int *)malloc(n*sizeof(int));//创建n个标记
    	int count = 0;
    	//int  arr[n];//error
    	int i;
    	for(i=0;i<n;i++)//1是素数,0不是素数
    	{
        
    		arr[i] = 1;
    	}
    
    	arr[0] = arr[1] = 0;//0,1不参与
    	for(i=2;i<n;i++)
    	{
        
    		for(int j=i+1;j<n;j++)//遍历i后面所有的元素,判断是否为i的倍数,如果是则不是素数
    		{
        
    			if(j%i == 0)//j不是素数
    			{
        
    				arr[j] = 0;
    			}
    		}
    	}
    
    	for(i=0;i<n;i++)
    	{
        
    		if(arr[i] == 1)
    		{
        
    			count++;
    		}
    	}
    	int *brr = (int *)malloc(count*sizeof(int));//存放素数
    
    	*rtlen = count;//输出参数,将数组的长度带出去
    
    	int j = 0;//brr下标
    	for(i=0;i<n;i++)
    	{
        
    		if(arr[i] == 1)
    		{
        
    			brr[j++] = i;
    		}
    	}
    	free(arr);
    	return brr;
    }
    
    
    int main()
    {
        
    	int len;
    	int *p = Primer(100,&len);
    	for(int i=0;i<len;i++)
    	{
        
    		printf("%d ",p[i]);
    		if(i%10 == 9)
    		{
        
    			printf("\n");
    		}
    	}
    	free(p);
    	Primer1(100);
        Sushu1();
        Sushu2();
    	return 0;
    }