因数和倍数，质数和合数，因数倍数质数合数的有关概念是什么

目录 质数与合数一、概念1.质数2.合数 二、质数判定1. O ( n ) O(\\sqrt{n}) O(n ?)算法，暴力枚举 三、批量求质数1.埃氏筛法2.欧拉线性筛

质数与合数 一、概念 1.质数

如果一个数只有1和他本身

两

个因数，那这个数就是质数。

例：7 = 1 x 7，5 = 1 x 5。

2.合数

如果一个数除了1和他本身，还有其他因数，那这个数就是合数。

例：8 = 1 x 8 = 2 x 4，12 = 1 x 12 = 2 x 6 = 3 x 4。

1既不是质数，也不是合数

二、质数判定 1. O ( n ) O(\\sqrt{n}) O(n ?)算法，暴力枚举

就是从2开始，一直到根号 n \\sqrt{n} n ?，判断每一个数是不是n的因数。如果是的话n就不是质数了。

bool prime(int n){for(int i = 2; i * i