[C language] screening method for prime numbers

---

subject

describe

Using screening method to find n Prime number within . The solution process of screening method is ： take 2~n Positive integers between are stored in the array memory , Will be in the array 2 Everything after that can be 2 The number of divisions 0, then 3 Everything after that can be 3 The number of divisions 0 , And so on , until n until . Array is not 0 The number of is prime .

Input description

Multi group input , Enter a positive integer on each line （ No more than 100）.

Output description

The integer entered for each line n, Output two lines , first line , Output n within （ Include n） The prime , Separate... With spaces

Example

Input ：20
Output ：
2 3 5 7 11 13 17 19
11

One 、 Ideas

The common method of finding and judging prime numbers is trial division , There is also the use of sqrt or 1/2. The screening method is similar to the trial division method , Every number is divided by 1 And numbers other than itself . The key to the screening method is ：（1） The request will 2-n The number of is stored in the array first ;（2） Will be 2 After that , Note that 2 Later numbers can be 2 Zeroing of integer division , Then move back one bit , from 3 Start , Will be 3 Later can be 3 Zeroing of integer division , By analogy , until n. In short, the first point is the array 2 after 3, One round of loop traversal divided by 2 after , The position that the array first points to is backward 1, Pointing to the array 3 After 4, Consider how to balance the cycle i and j Value .

Two 、 Code implementation

#include<stdio.h>
int main()
{
    
    int n;
    int count=0;
    int arr[100]={
    0};
    while(scanf("%d",&n)!=EOF)
    {
    
        int j=0;
        int i=0;
        for(i=2;i<=n;i++)
        {
    
            arr[j++]=i;// assignment 
            //arr[0]=2,arr[1]=3...arr[18]=20
        }
        // Zero clearing 
        for(i=2;i<=n;i++)// Change of divisor 
        {
    
            for(j=i-1;j<n-1;j++)// The change of the dividend 
            {
    // The first number is +1 Changing , So we use i
                if(arr[j]%i==0)
                {
    
                    arr[j]=0;
                }
            }
        }
        // Print 
        // Because one more number will be initialized , therefore i<n-1
        for(i=0;i<n-1;i++)
        {
    
            if(arr[i]!=0)
            {
    
                count++;
                printf("%d ",arr[i]);
            }
        }
        printf("\n%d\n",n-1-count);
    }
    return 0;
}