素数

暴力法

从2到num-1枚举每个数，看是否能被num整除。如果能被整除，说明num不是素数。如果遍历完整个循环仍然找不到num能被整除的数，说明num是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    int num;
    scanf("%d", &num);
    int i = 0;
    for (i = 2; i <= num-1; i++)
    {
        if (num % i == 0)
        {
            break;
        }
    }
    if (i == num)
    {
        printf("%d is a prime number.", num);
    }
    else
    {
        printf("%d is not a prime number.", num);
    }

    return 0;
}

使用中间数isPrime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main()
{
    int num = 0;
    scanf("%d", &num);
    int isPrime = 1;
    int i = 0;
    if (num <= 1)
    {
        isPrime = 0;
    }
    else
    {
        for (i = 2; i <= num-1; i++)
        {
            if (num % i == 0)
            {
                isPrime = 0;
                break;
            }
        }
    }

    if (isPrime)
    {
        printf("%d is a prime number.", num);
    }
    else
    {
        printf("%d is not a prime number.", num);

    }

    return 0;
}

2 ~ num/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    int num = 0;
    int i = 0;
    scanf("%d", &num);

    for (i = 2; i <= num / 2; i++)
    {
        if (num % i == 0)
        {
            break;
        }
    }
    if (i == num / 2 + 1)
    {
        printf("%d is a prime number", num);
    }
    else
    {
        printf("%d is not a prime nuber.", num);
    }

    return 0;
}

开方法

在判断素数的时候，一般从2开始循环到根号下的数，如果在这个范围内找到了一个数能够整除num，则num不是素数。如果在该范围内都没有找到，则num是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    int i = 0;
    int num = 0;
    scanf("%d", &num);
    int limit = sqrt(num);
    for (i = 2; i <= limit; i++) 
    {
        if (num % i == 0)
        {
            break;
        }
    }
    if (i > limit)
    {
        printf("%d is a prime number", num);
    }
    else
    {
        printf("%d is not a prime number", num);
    }

    return 0;
}

100以内素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
	int num = 0, i = 0;
	for (num = 2; num < 100; num++)
	{
		for (i = 2; i <= (int)sqrt(num); i++)
		{
			if (num % i == 0)
			{
				break;
			}
		}
		if (i > (int)sqrt(num))
		{
			printf("%d ", num);
		}
	}

	return 0;
}