【R语言】计算100以内素数的8种方法

目录

• 1 前言
• 2 素数
• 3 计算方法
• • 3.1 埃拉托色尼筛法
  • 3.2 费马小定理
  • 3.3 试除法
  • 3.4 费马-米勒素性检验
  • 3.5 素数筛法
  • 3.6 布莱克-霍尔素性检验
  • 3.7 对数表方法
  • 3.8 线性筛法
• 参考

1 前言

无前言，上周五有个大一的学生问到。虽然是很简单的数学问题，但是挺有趣的，整理了一下：

2 素数

素数，也称为质数，是指除了1和本身之外，没有其他正整数可以整除它的数。例如，2、3、5、7、11等都是素数，而4、6、8、9等都不是素数。素数在数论和计算机科学中都有广泛的应用，例如加密算法、随机数生成、哈希表等领域。求解素数一直是数学和计算机领域的热门问题之一。由于素数的特殊性质，它们具有重要的理论和实际应用价值。

3 计算方法

3.1 埃拉托色尼筛法

该方法利用素数的倍数都不是素数的特性，不断排除非素数，留下素数。

# Eratosthenes sieve
n <- 100
prime <- rep(TRUE, n)
prime[1] <- FALSEfor (i in 2:sqrt(n)) {if (prime[i]) {for (j in i^2:n) {if (j %% i == 0) {prime[j] <- FALSE}}}
}which(prime)

3.2 费马小定理

该方法通过费马小定理判断一个数是否为素数，但只适用于比较小的数。

# Fermat's little theorem
n <- 100
prime <- c()for (i in 2:n) {if (i^(n-1) %% n == 1) {prime <- c(prime, i)}
}prime

3.3 试除法

该方法逐个试除每个数是否能整除，如果不能整除，则为素数。

# Trial division
n <- 100
prime <- c()for (i in 2:n) {if (all(i %% 2:(i-1) != 0)) {prime <- c(prime, i)}
}prime

3.4 费马-米勒素性检验

该方法是一种基于费马小定理的概率算法，能够快速判断大数是否为素数。

# Miller-Rabin primality test
library(numbers)
n <- 100
prime <- c()for (i in 2:n) {if (isprime(i)) {prime <- c(prime, i)}
}prime

3.5 素数筛法

该方法使用筛法，将非素数标记为已筛除，最终留下素数。

# Sieve of Sundaram
n <- 50
sieve <- 1:(n/2)
prime <- c(2)for (i in 1:length(sieve)) {j <- iwhile ((sieve[i] + sieve[j] + 2 * sieve[i] * sieve[j]) <= n) {sieve[sieve[i] + sieve[j] + 2 * sieve[i] * sieve[j] - 1] <- 0j <- j + 1}
}prime <- c(prime, 2 * sieve[sieve != 0] + 1)prime

3.6 布莱克-霍尔素性检验

该方法是一种基于费马小定理和平方剩余的概率算法，能够快速判断大数是否为素数。

# Baillie-PSW primality test
library(numbers)
n <- 100
prime <- c()for (i in 2:n) {if (isprime(i)) {prime <- c(prime, i)}
}prime

3.7 对数表方法

该方法通过对数表找出所有的素数。

# Prime number table
n <- 100
prime <- c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)prime[prime <= n]

3.8 线性筛法

该方法将合数表示为质数和质数的积的形式，避免了重复筛除的问题。

# Linear sieve
n <- 100
prime <- c()
composite <- rep(FALSE, n+1)for (i in 2:n) {if (!composite[i]) {prime <- c(prime, i)}for (j in 1:length(prime)) {if (i * prime[j] > n) {break}composite[i * prime[j]] <- TRUEif (i %% prime[j] == 0) {break}}
}prime

参考

1. R Cookbook, 2nd Edition by Paul Teetor
2. R Graphics Cookbook, 2nd Edition by Winston Chang
3. R in Action, 2nd Edition by Robert I. Kabacoff
4. R Programming for Data Science by Roger D. Peng
5. Granville, A. (2019). Analytic number theory. American Mathematical Society.
6. Diamond, H. G., & Shurman, J. (2013). A first course in modular forms (Vol. 228). Springer Science & Business Media.
7. Baker, R. C. (1990). Exponential sums and the Riemann zeta function (Vol. 124). Cambridge University Press.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！