Multiple optimization methods print prime numbers between 100 and 200

Print 100~200 The prime between

Multiple optimization methods print 100~200 The prime between .

---

This paper uses four methods to print 100~200 The prime between , If it is helpful to you, you can pay attention to plus three companies , Continuous updating .

One 、 Title Overview

---

Print 100~200 The prime between .
prime number ： Prime number , except 1 And myself , There is no other divisor , Then the data is prime .

Two 、 Method

Method 1 ： Trial division

Try the idea of division ：
Because we're going to 100 to 200 The prime between , And 100 It's definitely not prime , So set variables i The range of phi is zero 101~200, Set another variable j, Because any number can be 1 Aliquot so j from 2 Start , If j<i, Will judge i%j Is it equal to 0, If it is equal to 0 shows i Not primes ,break Jump out then i++; If j and i equal , explain [2, i） All data between cannot be i to be divisible by , be i As a prime number

The code is as follows （ Example ）：

 Ideas ：
 prime number ： Prime number , except 1 And myself , There is no other divisor , Then the data is prime , The specific way is as follows 
*/
 
 
// Method 1 ： Trial division 
int main()
{
    
	int i = 0;
	int count = 0;
 
 
    //  The outer loop is used to get 100~200 All data between ,100 It's definitely not prime , therefore i from 101 Start 
	for(i=101; i<=200; i++)
	{
    
		// Judge i Prime or not ： use [2, i) Every data between is i except , As long as one can be divisible , It's not a prime number 
		int j = 0;
		for(j=2; j<i; j++)
		{
    
			if(i%j == 0)
			{
    
				break;
			}
		}
        
		//  After the above cycle , If j and i equal , explain [2, i） All data between cannot be i to be divisible by , be i As a prime number 
		if(j==i)
		{
    
			count++;
			printf("%d ", i);
		}
	}
 
 
	printf("\ncount = %d\n", count);
	return 0;
}

Defects of trial and error method ： Through the analysis of these data , Find more than i/2 The data is definitely not i Multiple , This method does many meaningless operations , We should try to improve .

Method 2

For method one （ Trial division ） The optimization of the , Get the data , Just test 【2,i/2】 Whether there are elements in the interval of can be divisible .

The code is as follows （ Example ）：

int main()
{
    
	int i = 0;//
	int count = 0;
	for(i=101; i<=200; i++)
	{
    
		// Judge i Prime or not 
		//2->i-1
		int j = 0;
		for(j=2; j<=i/2; j++)
		{
    
			if(i%j == 0)
			{
    
				break;
			}
		}
		//...
		if(j>i/2)
		{
    
  		count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;

}

Method 2 still contains some duplicate data , To optimize the ：

Method 3

Method 3 ： If i It can be [2, sqrt(i)] Any data division between , be i Not primes .
reason ： If m Can be 2 ~ m-1 Divide by any integer , The second factor must have one less than or equal to sqrt(m), The other is greater than or equal to sqrt(m).

int main()
{
    
	int i = 0;
	int count = 0;
	for(i=101; i<=200; i++)

	{
    
		// Judge i Prime or not 
		//2->i-1
		int j = 0;
		for(j=2; j<=sqrt(i); j++)
		{
    

			if(i%j == 0)
			{
    
				break;
			}
		}
		//...
		if(j>sqrt(i))
		{
    
			count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}

Continue to optimize method 3

Method four

as long as i Don't be [2, sqrt(i)] Divide any data between , be i Prime number , But in practice i Don't go from 101 Gradually increase to 200, Because something happened 2 and 3 outside , No two consecutive adjacent data are prime numbers at the same time .

int main()
{
    
	int i = 0;
	int count = 0;
	for(i=101; i<=200; i+=2)
	{
    
		// Judge i Prime or not 
		//2->i-1
		int j = 0;
		for(j=2; j<=sqrt(i); j++)
		{
    
			if(i%j == 0)
			{
    
				break;
			}
		}
		//...
		if(j>sqrt(i))
		{
    
			count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}

summary

   Here are four ways to judge and print 100~200 The prime , Each method is the optimization of the former method . If it is useful to everyone , You can pay attention to plus three , Continuous updating , You can also send me a private letter ~