Print primes between 100 and 200

“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

❗ prime ❕

Prime: A number that is divisible only by 1 and itself. Note: 1 is not prime

If 🔑 is a prime number, it is proved by repeated division until 🔑 is eliminated

#include<stdio.h>
int main(a)
{
    int i = 0;
    int j = 0;
    for(i = 100; i <= 200; i++)
    {
	// Check whether I is prime
	// Try to divide the interval: 2->i-1
	for(j = 2; j < i; j++)// This excludes 1 and the prime numbers themselves
	{
            if (i % j == 0)
                break;
            if(i % j ! =0 && j == i - 1)
		printf("%d ", i); }}return 0;
}
Copy the code

---

🔑 optimization: if a number that is not prime satisfies the condition (divisible by 1 and itself), it is not prime 🔑

#include<stdio.h>
int main(a)
{
    int i = 0;
    int j = 0;
    for(i = 100; i <= 200; i++)
    {
	for(j = 2; j < i; j++)
	{
            // non-prime, just break
            if (i % j == 0)
                break;
	}
	// This shows that I has separated all the numbers, so this number is prime
	if (i == j)
            printf("%d ", i);
    }
    return 0;
}
Copy the code

🔑 Use flag. This is another approach – each problem may have a different solution, think about solving the problem from all angles 🔑

#include<stdio.h>
int main(a)
{
    int i = 0;
    int j = 0;
    for(i = 100; i <= 200; i++)
    {
	int flag = 1;// Give 1 tag
	for(j = 2; j < i; j++)
	{
            if (i % j == 0)
            {
                flag = 0;// Assign the token to 0 if it is prime
		break; }}if (1 == flag)//1 is prime, 0 is not prime
            printf("%d ", i);
    }
    return 0;
}
Copy the code

---

🔑 optimization idea: reduce the number of trial division m = a * b a and b at least one of the numbers is <= square m; If I find one factor that divisible m before I square m, I don’t have to find another factor 16 is 2 times 8 is 4 times 4 which means if I find 2 that divisible 16, I don’t have to go into 8 to see if it goes into 16. I used to go into 2 -> I – 1; Now try dividing between 2 -> SQRT (I) 🔑

#include<stdio.h>
#include<math.h>
int main(a)
{
    int i = 0;
    int j = 0;
    for (i = 100; i <= 200; i++)
    {
	int flag = 1;
	for (j = 2; j <= sqrt(i); j++)// SQRT is the square root function whose header is math
	{
            if (i % j == 0)
            {
                flag = 0;
		break; }}if (1 == flag)
            printf("%d ", i);
    }
    return 0;
}
Copy the code

---

🔑 Reoptimization: Can even numbers be prime? – Of course not 🔑

#include<stdio.h>
#include<math.h>
int main(a)
{
    int i = 0;
    int j = 0;
    for (i = 101; i <= 200; i+=2)//101, 103, 105, 107... (Skip even numbers at source)
    {
	int flag = 1;
	for (j = 2; j <= sqrt(i); j++)// SQRT is the square root function whose header is math
	{
            if (i % j == 0)
            {
		flag = 0;
		break; }}if (1 == flag)
            printf("%d ", i);
    }
    return 0;
}
Copy the code

🔑 reoptimize… . Well, learning is useless learning is useless… Of course, if you have other methods, I hope you can share it to learn 🔑

// You are welcome to add
// You are welcome to add
Copy the code