目录
方法 2: 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）
方法 2:使用埃拉托斯特尼筛法（Sieve of Eratosthenes）
方法 2:埃拉托斯特尼筛法（Sieve of Eratosthenes）
题目：求100之内的素数。
程序分析：质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
C 语言实现
方法 1: 使用 for 循环
#include <stdio.h>
#include <math.h>
int main() {
int i, j, k, n = 0; // 定义变量
for (i = 2; i <= 100; i++) { // 遍历从 2 到 100 的每个整数
k = (int)sqrt(i); // 计算 i 的平方根
for (j = 2; j <= k; j++) // 检查 i 是否能被 2 到 k 之间的任何数整除
if (i % j == 0) break; // 如果能整除，说明 i 不是素数，跳出内层循环
if (j > k) { // 如果 j 超过 k，说明 i 是素数
printf("%d ", i); // 打印素数
n++; // 素数计数器加一
if (n % 5 == 0) // 每打印 5 个素数换行
printf("\n");
}
}
return 0; // 程序结束
}
- 该程序使用了简单的算法来检查每个数字是否为素数。
- 它通过检查从 2 到该数字平方根的所有整数来判断一个数是否为素数。
- 每找到 5 个素数就换行，以便输出格式更整齐。
方法 2: 使用埃拉托斯特尼筛法
- 使用更高效的素数检测算法：对于较大的范围，可以考虑使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来生成素数，这样效率更高。
- 代码可读性：可以增加注释，或者将部分逻辑封装成函数，以提高代码的可读性和可维护性。
- 输出格式：可以在输出的最后添加换行符，以使输出更整洁。
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int main() {
bool isPrime[MAX + 1]; // 创建一个布尔数组来标记素数
for (int i = 0; i <= MAX; i++) {
isPrime[i] = true; // 初始化所有数为素数
}
isPrime[0] = isPrime[1] = false; // 0 和 1 不是素数
for (int i = 2; i * i <= MAX; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= MAX; j += i) {
isPrime[j] = false; // 标记 i 的倍数为非素数
}
}
}
int count = 0;
for (int i = 2; i <= MAX; i++) {
if (isPrime[i]) {
printf("%d ", i);
count++;
if (count % 5 == 0) {
printf("\n"); // 每打印 5 个素数换行
}
}
}
printf("\n"); // 最后换行
return 0;
}
- 这个改进后的版本使用了布尔数组
isPrime来标记每个数字是否为素数。 - 通过筛法，所有非素数的标记都被设置为
false，最终只输出标记为true的数字。 - 这种方法在处理较大范围的素数时效率更高。
方法 3: 使用自定义判断素数
#include <stdio.h>
#include <math.h>
int isPrime(int num) {
if (num < 2) return 0; // 0 和 1 不是素数
if (num == 2) return 1; // 2 是素数
if (num % 2 == 0) return 0; // 排除偶数
for (int j = 3; j <= sqrt(num); j += 2) { // 只检查奇数
if (num % j == 0) return 0; // 如果能被整除，返回 0
}
return 1; // 是素数
}
int main() {
int n = 0; // 素数计数器
for (int i = 2; i <= 100; i++) {
if (isPrime(i)) {
printf("%d ", i);
n++;
if (n % 5 == 0) {
printf("\n"); // 每打印 5 个素数换行
}
}
}
printf("\n"); // 最后换行
return 0;
}
Python 实现
方法 1: 使用自定义函数判断素数
这个 Python 程序将打印 2 到 100 之间的所有素数
import math
def is_prime(num):
if num < 2:
return False
for j in range(2, int(math.sqrt(num)) + 1):
if num % j == 0:
return False
return True
def main():
n = 0 # 素数计数器
for i in range(2, 101): # 遍历从 2 到 100 的每个整数
if is_prime(i): # 检查 i 是否为素数
print(i, end=' ') # 打印素数
n += 1 # 素数计数器加一
if n % 5 == 0: # 每打印 5 个素数换行
print() # 换行
print() # 最后换行
if __name__ == "__main__":
main() # 调用主函数
- 导入模块：使用
import math来导入数学模块，以便使用math.sqrt()函数计算平方根。 is_prime函数：这个函数用于检查一个数字是否为素数。它返回True如果是素数，返回False如果不是。main函数：这是程序的主函数，遍历从 2 到 100 的每个整数，调用is_prime函数来检查每个数字是否为素数。- 打印素数：如果是素数，则打印该数字，并在每打印 5 个素数后换行。
- 程序入口：使用
if __name__ == "__main__":来确保主函数在脚本直接运行时被调用。
方法 2: 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）
这种方法是生成素数的高效算法，适合处理较大的范围。
def sieve_of_eratosthenes(max_num):
is_prime = [True] * (max_num + 1) # 创建布尔数组
is_prime[0] = is_prime[1] = False # 0 和 1 不是素数
for i in range(2, int(max_num**0.5) + 1):
if is_prime[i]:
for j in range(i * i, max_num + 1, i):
is_prime[j] = False # 标记 i 的倍数为非素数
return [i for i in range(2, max_num + 1) if is_prime[i]] # 返回素数列表
def main():
primes = sieve_of_eratosthenes(100) # 获取 2 到 100 的素数
for index, prime in enumerate(primes):
print(prime, end=' ')
if (index + 1) % 5 == 0: # 每打印 5 个素数换行
print()
print() # 最后换行
if __name__ == "__main__":
main()
方法 3: 使用递归方法
def is_prime(num, divisor=2):
if num < 2:
return False
if divisor > int(num**0.5):
return True
if num % divisor == 0:
return False
return is_prime(num, divisor + 1)
def main():
for i in range(2, 101):
if is_prime(i):
print(i, end=' ')
print() # 最后换行
if __name__ == "__main__":
main()
Java 实现
方法 1: 使用自定义函数判断素数
这个 Java 程序将打印 2 到 100 之间的所有素数，功能与 C 代码相同。
public class PrimeNumbers {
public static void main(String[] args) {
int n = 0; // 素数计数器
for (int i = 2; i <= 100; i++) { // 遍历从 2 到 100 的每个整数
if (isPrime(i)) { // 检查 i 是否为素数
System.out.print(i + " "); // 打印素数
n++; // 素数计数器加一
if (n % 5 == 0) { // 每打印 5 个素数换行
System.out.println();
}
}
}
System.out.println(); // 最后换行
}
// 检查一个数是否为素数
public static boolean isPrime(int num) {
if (num < 2) return false; // 0 和 1 不是素数
int k = (int) Math.sqrt(num); // 计算 num 的平方根
for (int j = 2; j <= k; j++) { // 检查 num 是否能被 2 到 k 之间的任何数整除
if (num % j == 0) return false; // 如果能整除，返回 false
}
return true; // 是素数
}
}
- 主类：定义了一个名为
PrimeNumbers的公共类。 main方法：程序的入口点，遍历从 2 到 100 的每个整数，调用isPrime方法来检查每个数字是否为素数。- 打印素数：如果是素数，则打印该数字，并在每打印 5 个素数后换行。
isPrime方法：这个方法用于检查一个数字是否为素数。它返回true如果是素数，返回false如果不是。- 平方根计算：使用
Math.sqrt()方法计算平方根。
方法 2:使用埃拉托斯特尼筛法（Sieve of Eratosthenes）
这种方法是生成素数的高效算法，适合处理较大的范围。
public class PrimeNumbers {
public static void main(String[] args) {
int max = 100;
boolean[] isPrime = new boolean[max + 1]; // 创建布尔数组
for (int i = 2; i <= max; i++) {
isPrime[i] = true; // 初始化所有数为素数
}
for (int i = 2; i * i <= max; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false; // 标记 i 的倍数为非素数
}
}
}
int count = 0; // 素数计数器
for (int i = 2; i <= max; i++) {
if (isPrime[i]) {
System.out.print(i + " "); // 打印素数
count++;
if (count % 5 == 0) {
System.out.println(); // 每打印 5 个素数换行
}
}
}
System.out.println(); // 最后换行
}
}
方法 3:递归方法
public class PrimeNumbers {
public static void main(String[] args) {
for (int i = 2; i <= 100; i++) {
if (isPrime(i, 2)) { // 检查 i 是否为素数
System.out.print(i + " "); // 打印素数
}
}
System.out.println(); // 最后换行
}
// 递归检查一个数是否为素数
public static boolean isPrime(int num, int divisor) {
if (num < 2) return false; // 0 和 1 不是素数
if (divisor * divisor > num) return true; // 如果没有找到因数，返回 true
if (num % divisor == 0) return false; // 如果能整除，返回 false
return isPrime(num, divisor + 1); // 递归检查下一个因数
}
}
方法 4: 使用 Java 8 的流（Streams）
利用 Java 8 的流特性来生成素数。
import java.util.stream.IntStream;
public class PrimeNumbers {
public static void main(String[] args) {
IntStream.rangeClosed(2, 100) // 生成 2 到 100 的整数流
.filter(PrimeNumbers::isPrime) // 过滤出素数
.forEach(num -> System.out.print(num + " ")); // 打印素数
System.out.println(); // 最后换行
}
// 检查一个数是否为素数
public static boolean isPrime(int num) {
if (num < 2) return false; // 0 和 1 不是素数
return IntStream.rangeClosed(2, (int) Math.sqrt(num)) // 生成 2 到 sqrt(num) 的整数流
.noneMatch(divisor -> num % divisor == 0); // 检查是否有因数
}
}
Js 实现
这个 JavaScript 程序将打印 2 到 100 之间的所有素数
方法 1: 使用自定义函数判断素数
function isPrime(num) {
if (num < 2) return false; // 0 和 1 不是素数
const k = Math.sqrt(num); // 计算 num 的平方根
for (let j = 2; j <= k; j++) { // 检查 num 是否能被 2 到 k 之间的任何数整除
if (num % j === 0) return false; // 如果能整除，返回 false
}
return true; // 是素数
}
function main() {
let n = 0; // 素数计数器
for (let i = 2; i <= 100; i++) { // 遍历从 2 到 100 的每个整数
if (isPrime(i)) { // 检查 i 是否为素数
process.stdout.write(i + " "); // 打印素数
n++; // 素数计数器加一
if (n % 5 === 0) { // 每打印 5 个素数换行
console.log();
}
}
}
console.log(); // 最后换行
}
main(); // 调用主函数
isPrime函数：这个函数用于检查一个数字是否为素数。它返回true如果是素数，返回false如果不是。- 如果数字小于 2，返回
false。 - 计算数字的平方根，并检查从 2 到平方根之间的所有整数是否能整除该数字。
- 如果数字小于 2，返回
main函数：这是程序的主函数，遍历从 2 到 100 的每个整数，调用isPrime函数来检查每个数字是否为素数。- 如果是素数，则打印该数字，并在每打印 5 个素数后换行。
process.stdout.write：用于在控制台上打印输出，而不自动换行。这样可以更好地控制输出格式。console.log()：用于在最后输出一个换行符。
方法 2:埃拉托斯特尼筛法（Sieve of Eratosthenes）
function sieveOfEratosthenes(max) {
const isPrime = Array(max + 1).fill(true); // 创建布尔数组
isPrime[0] = isPrime[1] = false; // 0 和 1 不是素数
for (let i = 2; i * i <= max; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= max; j += i) {
isPrime[j] = false; // 标记 i 的倍数为非素数
}
}
}
return isPrime.map((prime, index) => prime ? index : null).filter(Boolean); // 返回素数列表
}
function main() {
const primes = sieveOfEratosthenes(100); // 获取 2 到 100 的素数
let n = 0; // 素数计数器
primes.forEach(prime => {
process.stdout.write(prime + " "); // 打印素数
n++;
if (n % 5 === 0) {
console.log(); // 每打印 5 个素数换行
}
});
console.log(); // 最后换行
}
main(); // 调用主函数