In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a simple, ancient algorithm for finding all prime numbers up to a specified integer.[1] It works efficiently for the smaller primes (below 10 million).[2] It was created by Eratosthenes, an ancient Greek mathematician. However, none of his mathematical works survived—the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.
A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.
[素数的定义是,一个仅能被1和本身整除的自然数]
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
[可以通过以下的埃拉托色尼筛选法寻求所有小于整数n的素数]
Create a list of consecutive integers from two to n: (2, 3, 4, ..., n). [列出从2到n的一串连续自然数]
Initially, let p equal 2, the first prime number. [开始,先把2当作第一个素数,并赋值给变量p]
Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.) [将该列自然数中划掉p的倍数]
Find the first number remaining on the list after p (this number is the next prime); replace p with this number. [将剩下的自然数按原来顺序重新组成新的一列,并将第一个数赋给变量p]
Repeat steps 3 and 4 until p2 is greater than n. [重复第三第四步,直到p的平方大于n]
All the remaining numbers in the list are prime. [剩下的自然数就是所有小于n的素数]
public static List<Long> find_prime_below_number(long number){
int exe_number = 0;
boolean close = false;
List<Long> numberSet = new ArrayList<Long>();
List<Long> resultSet = new ArrayList<Long>();
for(long i=3; i<number; i+=2){
numberSet.add(i);
exe_number++;
}
double half = Math.sqrt(number);
do{
Long curN = numberSet.get(0);
resultSet.add(curN);
for(int j=0; j<numberSet.size(); j++){
exe_number++;
long l = numberSet.get(j);
if(l%curN==0){
numberSet.remove(j);
}
}
if(curN>half){
close = true;
}
}while(!close&&numberSet.size()!=0);
if(numberSet.size()!=0){
for(Long n : numberSet){
exe_number++;
resultSet.add(n);
}
}
System.out.println("exe_number:"+exe_number);
return resultSet;
}
当找1000000以下的素数时,执行就挂了
肯定有问题
因为原算法说了是10 million
以下的数字~
一千万以下啊~
想办法解决
分享到:
相关推荐
SieveOfEratosthenes
采用Sieve of Eatosthenes (埃拉托色尼筛选法)方法搜索素数小程序。(c++实现)
Algorithm-sieve-of-eratosthenes.zip,Eratosthenes JavaScript实现的筛选,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
使用python编写的Eratosthenes筛选。
埃拉托色尼筛一个 android 应用程序,用户可以输入一个大于 1 的数字并找到 2 和该数字之间的所有质数。
求素数问题。埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂的整数,编程实现此算法,并讨论运算时间。
Java实现埃氏筛法的程序,快速求出100以内素数,适合初学者参考
在C#中,一个常见的解决方案是使用埃拉托斯特尼筛法(Sieve of Eratosthenes),这是一种高效的算法,用于找出小于给定数的所有质数。 埃拉托斯特尼筛法原理 埃拉托斯特尼筛法的基本思想是从最小的质数开始,逐个...
一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes) ,说简单一点就是画表格,然后删表格,如图所示: 从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除...
埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂ 的整数,编程实现此算法,并讨论运算时间。(1) 2. 猴子吃桃子问题。有一群猴子摘了一堆桃子,...
primesieve每个筛选质数使用8个字节,因此其内存使用量约为 每个线程的字节数。安装可以使用操作系统的程序包管理器来安装primesieve命令行程序。 为了使用libprimesieve进行开发,您可能需要安装libprimesieve-dev...
对于几个流行的算法(prefix sum,matrix multiplication,Gaussian elimination,Sieve of Eratosthenes)的串行算法和openMP并行算法的代码,以及性能测试的实验报告
筛玩Eratosthenes筛
For this assignment, implement the Sieve of Eratosthenes using a pool of processes in Python, use test runs to see how quickly the program runs under different combinations of parameters, and write a ...
计算10^18素数筛法, 目前这个是国内最快的筛法程序(如果你有比我还快的, 个人给你500元奖励 * 快的倍数),比国外primesieve略慢20%, , 使用非常方便, 输入两个数得到素数个数, 共计3000行C++代码。采用10多...
java笔试题算法多种语言的埃拉托色尼筛子 以各种语言实现 Eratosthenes 筛以展示 GraalVM 和 Truffle 的强大功能。 请先下载后再进行实验。 已经过测试可以与版本19.3.1 。 Ruby速度 使用以下命令可以发现 GraalVM ...
埃拉托色尼筛 Android 实习编码挑战 描述 在我的代码中,我使用以下三行来禁用此应用程序的横向模式: getWindow().addFlags(WindowManager.LayoutParams.FLAG_KEEP_SCREEN_ON); setRequestedOrientation...
sieve, 雷鸟筛选插件 Thunderbird Sieve是服务器端邮件过滤功能的强大脚本语言。 它的目的是与 IMAP,因此它被广泛扩展。 许多IMAP服务器都能够运行筛选过滤器。 筛选器在服务器端存储并运行所有脚本。现在有一个...
Eratosthenes筛 这个小型项目是的,用于使所有素数都在阈值以下 建造 用make make 没有make mkdir bin gcc -o ./bin/primes src/primes.c -lm 跑步 正常运行 ./bin/primes 抑制输出 ./bin/primes --suppress-...