寻找100到n之间的素数有多种方法，不同的编程语言可能在实现上有所差异，但基本思路是相似的。以下是一些常见的算法思路和方法：
试除法：这是最简单直接的方法，通过尝试将每个数除以从2开始的所有较小的数，直到该数的平方根。如果在这个范围内没有发现除了1和它本身之外的除数，则该数是素数。
优化的试除法：在试除法的基础上，可以只试除以2开始的素数，因为如果一个数不是素数，它必定有一个素数因子。此外，只需试除到该数的平方根即可。
埃拉托斯特尼筛法（Sieve of Eratosthenes）：这是一种高效的算法，尤其适用于寻找一定范围内的所有素数。首先假设所有数都是素数，然后从最小的素数2开始，逐步筛去它们的倍数，剩下的就是素数。
埃拉托斯特尼筛法的优化版本：例如，只对奇数进行筛选，因为2是唯一的偶数素数。
线性筛法：这是埃拉托斯特尼筛法的一种变体，它使用一个数组来记录每个数字是否为素数，然后线性地遍历这个数组，对于每个素数，标记其倍数为非素数。
使用预先计算的素数表：如果n不是非常大，可以预先计算一个足够大的素数表，然后在这个表中查找100到n之间的所有素数。
C语言 - 试除法优化到平方根
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
int main() {
int n;
printf("Enter the upper limit: ");
scanf("%d", &n);
for (int i = 100; i <= n; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
return 0;
}
Python - 埃拉托斯特尼筛法
def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n+1, p):
primes[i] = False
p += 1
return [p for p in range(100, n+1) if primes[p]]
n = int(input("Enter the upper limit: "))
print("Prime numbers between 100 and", n, "are:", sieve_of_eratosthenes(n))
Java - 试除法
import java.util.*;
public class PrimeNumbers {
public static boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the upper limit: ");
int n = scanner.nextInt();
for (int i = 100; i <= n; i++) {
if (isPrime(i)) {
System.out.print(i + " ");
}
}
}
}
JavaScript - 试除法优化到平方根
function isPrime(num) {
if (num <= 1) return false;
for (let i = 2; i * i <= num; i++) {
if (num % i === 0) return false;
}
return true;
}
let n = prompt("Enter the upper limit:");
for (let i = 100; i <= Number(n); i++) {
if (isPrime(i)) {
console.log(i);
}
}
Go语言 - 埃拉托斯特尼筛法
package main
import (
"fmt"
"math"
)
func sieveOfEratosthenes(n int) []int {
primes := make([]bool, n+1)
for i := 2; i <= n; i++ {
primes[i] = true
}
for p := 2; p <= int(math.Sqrt(float64(n))); p++ {
if primes[p] {
for i := p * p; i <= n; i += p {
primes[i] = false
}
}
}
var primeNumbers []int
for i, isPrime := range primes[100:] {
if isPrime {
primeNumbers = append(primeNumbers, i+100)
}
}
return primeNumbers
}
func main() {
var n int
fmt.Print("Enter the upper limit: ")
fmt.Scan(&n)
primes := sieveOfEratosthenes(n)
fmt.Println("Prime numbers between 100 and", n, "are:", primes)
}
请注意，这些代码示例仅用于演示目的，实际使用时可能需要根据具体环境和需求进行调整。
