离散数学中的素数

概述

当且仅当 1 和 p 是 p 的唯一正除数时，大于 1 的整数 p 才被称为素数或质数。简单来说，如果一个数只能被 1 和它本身整除，那么它就是素数。如果大于 1 的整数 q 不是素数，则有一个术语称为合数。这意味着如果一个数能被任何其他数整除，那么它就是合数。换句话说，我们可以说，如果一个数不是素数，那么它就是合数。

例如

整数 4、6、8、9 称为合数，整数 2、3、5、7 和 11 称为素数。

定理 1

如果对于所有整数 x 和 y，p 都能整除 xy，那么大于 1 的整数 p 将被称为素数。这个陈述意味着对于素数 p，p 要么能整除 x，要么能整除 y。

定理 2

每个整数 n >= 2 都必须包含一个素因子。

定理 3

假设合数用 n 表示。在这种情况下，n 必须有一个不大于 √n 的素因子。

素数的例子如下所示

示例 1

在这个例子中，我们有两个整数，我们必须确定哪个是素数。第一个整数是 293，第二个整数是 9823。

解决方案

首先，我们将找出所有素数 p，使得 p² <= 293。所有这些素数是 2、3、5、7、11、13 和 17。现在，293 不能被这些素数中的任何一个整除。所以我们可以说 293 是素数。

现在我们将找出素数 p，使得 p² <= 9823。所有这些素数是 2、3、5、7、11、13、17 等。现在，9823 不能被 2、3、5、7 中的任何一个整除，但 11 能整除 9823。所以我们可以说 9823 不是素数。

示例 2

在这个例子中，我们将假设 n 是一个正整数，使得 n² - 1 是素数。这里我们必须找出整数 n。

这里 n² - 1 可以写成 n² - 1 = (n - 1) (n² + n -+1)。这是因为 n² - 1 是素数，要么 (n² + n -+1) = 1，要么 (n - 1) = 1。所以现在我们知道 n >= 1，所以 n² + n + 1 > 1，即 n² + n + 1 != 1。因此，我们必须有 n - 1 = 1。这个陈述表明 n = 2。

示例 3

在这个例子中，我们将假设 p 是一个素整数，使得 gcd (a, p³) = p 且 gcd (b, p⁴) = p。这里我们必须找出 gcd (ab, p⁷)。

解决方案

为了解决这个问题，我们将采用给定条件 gcd (a, p³) = p。这里，p | a，且 p² | a。（如果 p² | a，则会出现矛盾，因为 gcd (a, p³) = p² > p）。现在我们可以将 'a' 写成素数幂的乘积形式。这是因为 p | a 且 p² | a。这个陈述表明 p 在 'a' 的素因式分解中以因子的形式出现，但 p^k 不会出现在 'a' 的素因式分解中，因为 k >= 2。与 gcd (b, p⁴) = p 相同，这意味着 p | b，且 p² | b。与前面描述的相同，这个陈述表明 p 在 'a' 的素因式分解中以因子的形式出现，但 p^k 不会以 'a' 的素因式分解的形式出现，因为 k >= 2。现在可以得出结论，p² | ab，且 p³ | ab。总之，我们可以说 gcd (b, p⁷) = p²。

素性测试算法

示例

在这个例子中，我们将使算法更高效，36 =

修改后的算法

查找素数的算法

埃拉托斯特尼筛法是一种古老的算法，在数学中用于确定直到任意给定长度的所有素数。埃拉托斯特尼筛法的输入和输出如下所述

Input: an integer n > 1. 
Output: It will generate all prime numbers from 2 through n. 

Here we will assume an array A of Boolean values, which is indexed with the help of integers 2 to n, initially all set to true. 
 
for i = 2, 3, 4, ....., not exceeding √n do
   if A [i] is true
      for j = i2, i2 + i, i2 + 2i, i2 + 3i, ......, not exceeding n do
          A[j] := false

return all i such that A[i] is true.