Eratosthenes的筛子是动态编程的一个例子吗？
Eratosthenes的筛子是动态编程的一个例子。
Eratosthenes的筛子，也称为埃拉托斯特尼筛法，是一种用于找出一定范围内所有素数的算法。它通过逐步筛选掉非素数来实现。在动态编程中，算法的执行过程是逐步进行的，每一步的结果会影响到下一步的计算，因此Eratosthenes的筛子可以被视为动态编程的一个例子。
该算法的基本思想是从2开始，将所有的倍数标记为非素数，然后继续向后遍历，直到遍历完所有的数。最终，未被标记的数即为素数。
动态编程是一种编程范式，它将问题分解为一系列子问题，并通过保存子问题的解来避免重复计算，从而提高效率。Eratosthenes的筛子正是通过逐步筛选的方式，将问题分解为一系列的子问题，并在每一步中更新筛选结果，最终得到所有的素数。
Eratosthenes的筛子在计算素数时具有较高的效率，尤其适用于需要多次查询素数的场景。例如，在密码学中，素数的生成和验证是非常重要的，Eratosthenes的筛子可以用于快速生成素数表，并进行素数的验证。
腾讯云提供了多种云计算相关的产品和服务，其中包括计算、存储、数据库、人工智能等领域。具体推荐的产品和产品介绍链接地址可以根据具体需求进行选择，以下是一些常用的腾讯云产品：
- 云服务器（CVM）：提供弹性的虚拟服务器实例，适用于各种计算场景。产品介绍链接
- 云数据库MySQL版：提供高性能、可扩展的MySQL数据库服务。产品介绍链接
- 人工智能机器学习平台（AI Lab）：提供丰富的人工智能算法和模型，支持开发者进行机器学习和深度学习的实验和应用。产品介绍链接
请注意，以上推荐的腾讯云产品仅供参考，具体选择应根据实际需求和情况进行。
相关·内容
我有点困惑的是，Eratosthenes的筛子(用一个用于所有数字的数组和一个标记复合数字的循环来实现)是否是动态编程的一个例子？有几个朋友告诉我，它的实现方式是一个自下而上的DP的例子，但我很难看到它。子问题到底是什么，您将如何使用自顶向下/递归实现SoE？谢谢你们。
浏览 11提问于2018-02-28得票数 2
1回答
素数发生器
、、
这是一个素数生成器类，松散地基于Eratosthenes的筛子。它应该产生相当数量的素数(即百万)。
static class PrimesGenerator
{
private const int StartFrom = 2;
public static IEnumerable<int> GetPrimes()
{
var number = StartFrom;
var dividers = new List<int>();
while (true)
{
浏览 0提问于2018-06-15得票数 2
目前，我正在尝试比较两种不同的素数生成算法的平均运行时速度。我对Eratosthenes的筛子有一个天真的实现：
std::vector<int32_t> sieve_of_eratosthenes(int32_t n) {
std::vector<int32_t> primes;
std::vector<bool> sieve(n + 1, true);
for (int32_t i = 2; i * i <= n; i++) {
if (sieve[i]) {
for (int j =
浏览 16提问于2022-11-15得票数 3
我正在尝试用scala解决SPOJ中的问题(素数生成器)。但这让我想起了“时间有限”。有人知道这是为什么吗？
以下是我的代码。
var testCaseNumber = readInt()
for (index <- 1 to testCaseNumber) {
val range: Array[String] = readLine().split(" ")
(math.max(range(0).toInt, 2) to range(1).toInt).filter(num => {
var flag = true
for (elemen
浏览 2提问于2015-07-26得票数 1
我在一次面试中被问到了这个问题。我使用eratosthenes的sieve概念和一个数组实现了一个算法。
对于那些不知道筛子的人，有没有更好的方法来解决这个问题，这里是链接：
编辑:在时间和空间复杂度方面都是最好的。我只是告诉他们SoE的缺陷是空间复杂性。所以他们问我能不能做点什么。面试是这样进行的: 1)实现一个从1到n打印素数的算法:我使用SoE实现2)这是最好的方法吗？
浏览 1提问于2011-03-17得票数 5
回答已采纳
根据链接：，生成素数到n的素数列表的“sundaram”的运行时间给出了O(n*log(n))。这个算法比“筛选阿特金”要好吗?如果它对它的工作原理做了详细的阐述的话？
浏览 4提问于2011-03-08得票数 3
所以我花了一整晚的时间来组装这个基于埃拉托色尼筛子的质数生成器。代码如下：
n = input("What number do you want to calculate to? ")
import time
start = time.time()
def pr(l):
ln = l+1
p = range(2, ln)
for k in p:
f = range(k, ln, k)
for f in f[1:]:
if f in p:
p.remove(f)
return p
print pr(n)
end
浏览 2提问于2013-09-26得票数 1
我们被指派制作一个java程序，该程序与Eratosthenes算法的筛网并行。我已经用我所知道的每一种方式试过几次，但都没有成功。Im应该使用素数小于所计算的数的填充数组。这是我的代码，有人能帮我重新检查程序和/或找出为什么我要得到这个错误吗？任何帮助都是非常感谢的。
import java.text.DecimalFormat;
import java.util.Scanner;
import java.util.Arrays;
public class Lab6st
{
static int MAX = 100;
static int i;
static int k;
stati
浏览 5提问于2012-10-30得票数 1
我试图找出我能得到多少素数，直到最大2的乘积在Long.MAX_VALUE上为止。
它需要超过半个小时(和GBs的RAM)
public class Main {
public static void main(String[] args) {
ArrayList <Long> primes= new ArrayList<Long>();
primes.add(2L);
long i=3L;
// Looping from 3, to the limit
while (primes.
浏览 2提问于2016-12-30得票数 3
回答已采纳
我正在进行C编程任务，在不使用C的平方根函数的情况下实现Eratosthenes的筛子。下面是我的输出和我的教授的输出，我不确定我的代码中是什么导致了它的错误。有什么想法吗？
下面是预期的输出
Program initiated
1 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 101 103 107 109 113 127 131 137 139 149
151 157 163 167 173 179 181 191 193 1
浏览 0提问于2012-03-19得票数 2
回答已采纳
我似乎在使用合适的代码(或者一个我可以编辑和利用的基的例子)来使用Eratosthenes方法的筛子来找出质数的和时遇到了麻烦。我知道下面的代码更容易工作，但如果可能的话，我想要掌握更大的代码：
require 'prime'
Prime.each(1000).reduce(:+)
虽然有Eretosthenes筛子和sum的例子，但它们是在c++中的，因此对于Ruby来说是不可靠的。
浏览 0提问于2015-08-20得票数 0
在经历了一些 所以帖子 ，我发现 Eratosthenes的筛子 是生成质数的最好、最快的方法。 我想生成两个数字之间的质数，比方说 和 ..。 AFAIK，在Sieve的方法中，空间复杂度是 O(b) ..。 PS:我写了Big-O而不是Theta，因为我不知道空间需求是否可以减少。 我们能降低空间复杂度吗？ Eratosthenes的筛子 什么？
浏览 76提问于2012-09-15得票数 2
回答已采纳
最近我发现了一篇文章，声称它可以使用一个有效的Eratosthenes筛子在O(n)中找到小于n的所有素数。但是，我看不出它是怎么回事。
有人能帮忙吗？
浏览 4提问于2020-06-01得票数 0
回答已采纳
1回答
我的程序使用了大量的内存和处理能力，我只能搜索到6000，有什么方法可以减少使用的内存量？这将对未来的编程工作非常有帮助，因为知道如何巧妙地使用内存将是一件很好的事情。
ArrayList<Integer> factor = new ArrayList<Integer>();
ArrayList<Integer> non = new ArrayList<Integer>();
ArrayList<Integer> prime = new ArrayList<Integer>();
Scan
浏览 3提问于2017-05-04得票数 0
1回答
使用python的素数
、、、
我是编程新手，我决定做一些练习来提高我的能力。我坚持做一个练习：“找出两百万以下所有素数的和。”我的代码太慢了。
最初，我试图作为一个普通的素数问题来解决，结果是这样的：
sum = 2 + 3
for i in range (5, 2000000, 2):
for j in range (3, i, 2):
if i%j == 0:
break
else:
sum += i
print(sum)
这样，所有偶数都将被排除在循环之外。但这并没有解决我的问题。这里的震级真的很大。
所以我试着理解这段代码到底发生了什么。我在循
浏览 0提问于2016-01-22得票数 3
最近，我读了一些关于素数的文章，并决定编写自己的程序来寻找素数(不是为了学校或任何事情，只是出于爱好)。代码如下：
import time
a=[2,3]
e=[0,1,1,1,0,1]
b=0
c=0
d=[]
length=int(input("primes til n?"))
tijd=time.time()
while 1:
d=[]
b=(e.index(0,a[-1])+1)
a.append(b)
if len(e)<length:
e.extend(e*(b-1))
e[(b-1)]=1
if ((b
浏览 10提问于2017-07-14得票数 0
1回答
创建pi(x)表
、、、
设pi(x)表示素数<= x。例如，pi(100) = 25。我想要创建一个表来存储所有pi(x)的值。我想最快的办法就是用埃拉托斯提尼的筛子。首先标记所有素数，然后使用动态规划，对素数进行求和，每次出现新素数时都会增加。这是在以下Java代码中实现的：
public static int [] piTableSimple (int L)
{
int sqrtl = (int) Math.sqrt(L);
int [] piTable = new int [L + 1];
Arrays.fill(piTable, 1);
浏览 0提问于2019-08-28得票数 2
我正在研究euler项目中的问题46：
克里斯蒂安·戈德巴赫( Christian Goldbach )提出，每一个奇数组合数都可以写成素数和二次平方之和。9=7+ 2×1^2 15 =7+ 2×2^2 2 1=3+ 2×3^2 2 5=7+ 2×3^2 2 7= 19 + 2×2^2 33 = 31 + 2×1^2什么是最小的奇数组合，不能写成素数和二次平方的总和？
我的代码效率太低了，需要几分钟才能找到答案。(边界数只是粗略估计)
numbers = [(2*x**2) for x in list(range(1, 1000))]
normal = list(range(1, 100000
浏览 0提问于2017-06-30得票数 3
回答已采纳
这个程序求一个数的素因数的复杂度是多少？有什么方法可以改善它(只考虑时间复杂度，而不考虑编码标准或空间复杂度)。 谢谢并致以问候。 请参阅源代码： function primes(n) {
let primeNumbers = [2];
if (n < 2) {
return [];
} else if (n == 2) {
return [2];
}
for (let i = 3; i <= n; i++) {
let x = i;
let j = 0;
let isPrime = true;
whil
浏览 17提问于2019-02-27得票数 0
2回答
我需要打印所有小于给定数字n的素数。我可以使用Eratothenes筛子，但该算法的运行时间不是O(n)。这个问题有O(n)时间的解吗？
浏览 2提问于2012-03-15得票数 0
回答已采纳
2回答
我正在做作业，尽可能多地生成素数。我用Eratosthenes的筛子来生成小于1000万的素数。我想创造更多。怎样才能产生更多的素数？
浏览 5提问于2014-07-14得票数 0
回答已采纳
我17岁，在Python编程语言的帮助下开始编程。
我一直在寻求优化这个算法，可能是通过消除其中一个循环，或者使用更好的测试来检查质数。
在尝试计算和显示100000个质数时，脚本暂停了大约6秒，因为在将质数列表作为输出返回到控制台之前，它会用质数填充列表。
我一直在尝试使用
print odd,
简单地打印每个找到的质数，对于较小的输入(如n= 1000 )会更快，但对于n= 1000000，列表本身的打印速度要快得多(在python shell和控制台中)。
也许应该修改整个代码/算法，但脚本本质上应该保持不变:用户键入要打印的质数(n)，脚本返回直到第n个质数的所有质数。
from ti
浏览 1提问于2011-08-03得票数 5
4回答
我写了两个算法来求给定数的适当因子的和，以求完全数或富足数。
long sum_divisors_1(int a)
{
int i, t;
long sum = 1;
for (i = 2, t = sqrt(a); i < t + 1; i++) {
if (a % i == 0) {
sum += i;
sum += a / i;
}
}
if (a % t == 0)
sum -= t;
return sum;
}
long sum_diviso
浏览 1提问于2011-09-03得票数 2
回答已采纳
1回答
计算逐次素因式分解
、、、
每个人都知道分解是很困难的。但是如果我想要计算从2到N的每一个数的素因式分解呢？如果我们计算了2，n-1中每一个数的素数分解，如果一个数n有一个小素数因子，那么计算n的因式分解是容易的，因为大约73%的数可以被2、3或5整除。当然，有些情况下，例如当n是两个相似大小的素数的乘积时，仍然很困难，但平均来说，我们可以期望这个问题相当容易，因为我们只需要找到一个数的一个因子，就可以将我们的问题减少到我们以前解决的两个问题(即，分解d和n/d)。
我问这个问题是因为我感兴趣的是求正方形r( N ) ()之和，n的范围是0到N，它计算的是圆中整数点的数目。在Wolfram Mathworld页面上可以看
浏览 5提问于2015-11-18得票数 0
回答已采纳
3回答
在看了质数筛子代码，以及并发结构是如何工作的之后，我发现它非常优雅。然而，它的效率也非常低，而且IIRC，相当于通过将m除以小于m的每个数来测试m的可除性的O(n^2)操作。我认为我可以改为使用O(n^1.5)操作来检查m的可除性，方法是将m除以小于或等于sqrt(m)的每个数。然而，事实证明这比我预期的要难得多。
我知道这更多的是一个算法问题，但它也是一个与并发性极其相关的问题。如何实现算法的O(n^1.5)版本？
浏览 4提问于2011-02-06得票数 13
回答已采纳
5回答
Eratosthenes法的并行筛分法
使用Java，使用C/C++和
为2和4个核心CPU找到阈值的最佳值。
有人能帮我做这件事吗。我正在学习java &C/C++的线程。我需要什么东西来并行这个算法？
浏览 11提问于2012-02-16得票数 1
1回答
我目前正在开发一个程序，该程序使用PCSPIM在MIPS汇编中使用递归计算最多200个素数。到目前为止，我已经成功地填充了一个从1到200的数字数组和一个由所有1组成的二进制向量列表。我正在苦苦思索的概念是如何使用堆栈框架来帮助这个过程。
下面是我为堆栈帧准备的内容：
subu $sp,$sp,32 # Set up the stack frame
sw $ra, 28($sp) # save $ra register to the stack
sw $fp, 24($sp) # save $fp register to the stack
a
浏览 5提问于2014-10-10得票数 1
我研究了Eratosthenes的筛的工作，它用迭代法生成素数到给定的数，并去掉所有的合成数。算法只需迭代到sqrt(n)，其中n是我们需要找到所有素数的上界。我们知道，到n=10^9的素数数比合成数的数目要少得多。因此，我们使用所有的空间来判断这些数字不是素数，首先将它们标记为复合。我的问题是，我们是否可以修改算法来存储素数，因为我们处理的范围很大(因为素数非常少)？我们能直接储存质数吗？
浏览 12提问于2016-02-04得票数 2
我的任务是生成一个包含所有质数到12位数的数组。
我尝试通过首先创建一个函数enumerate来模拟，该函数生成一个包含从2到num的每个整数的数组
var enumerate = function(num) {
array = [];
for (var i = 2; i <= num; i++) {
array.push(i);
}
return array;
};
然后我做了一个函数leaveOnlyPrimes，它遍历并从数组中删除每个数组成员的倍数，直到1/2 max (这不会是每个整数，因为每次迭代数组都会变小)：
var lea
浏览 2提问于2013-08-10得票数 1
2回答
我遇到了Eratosthenes筛子的分段实现，它的运行速度将比传统版本快很多倍。有人能解释一下分段如何改善运行时间吗？注意，我想在1，b中找到素数。
它的作用是这样的：(寻找素数到10^9)
我们首先生成在sqrt(10^9)以下的筛分素数，这是交叉倍数所需要的。然后，我们开始将第一个素数2的倍数相交，直到达到2 >= segment_size的倍数，如果出现这种情况，我们使用(multiple - segment_size)计算下一段中该倍数的索引，并将其存储在一个单独的数组(next[])中。然后，我们使用相同的过程交叉下一个筛选素数的倍数。一旦我们在第一段中交叉了所有
浏览 1提问于2014-10-05得票数 4
回答已采纳
为了澄清，这与这个问题Sieve of Eratosthenes - Finding Primes Python不同，因为我不想在两个数字之间生成质数，但我想检查一个数字是否是质数。 我编写了以下代码来确定一个数字是否为质数。然后我听说了Eratosthenes算法的筛子，它显然更快，但我不知道如何在下面的代码中编写它？ number1 = int(raw_input("""
Enter any number :- """))
if number1 == 1:
print "1 is a special case. It is
浏览 20提问于2019-02-24得票数 0
2回答
C程序优化/提速
、、
作为一个初学者，我编写了一个程序来查找不高于输入自然数(x)的素数(prime)的个数。程序运行得很好(我认为)，但我想让它运行得更快(对于更高的数值)。这是可能的吗?如果是，是如何实现的？
#include <stdio.h>
int main() {
int x, i, j, flag = 1, prime = 0 ;
scanf("%d", &x);
for (i = 2; i <= x; i++) {
j = 2;
while (flag == 1 && j <
浏览 0提问于2015-10-17得票数 0
1回答
我有所有可以存储在32位unsigned int和中的素数，我想使用它们来生成64位素数。即使在逻辑和编译方面进行优化，使用试分区也太慢了。
我正在尝试修改Eratosthenes的Sieve，以处理预定义的列表，如下所示：
从2到4294967291在数组A中
在数组B中从2^32到X inc .1
找到C，它是当前素数的第一个倍数。
从C标记到当前质数跳跃到X。
转到1。
问题是第三步用模来求素数倍数，这样的运算就是我没有使用轨迹除法的原因。
是否有更好的方法来实现步骤3或整个算法。
谢谢。
浏览 6提问于2013-12-24得票数 2
回答已采纳
3回答
这段代码摘自"Haskell通向逻辑、数学和编程之路“一书。它实现了eratosthenes算法的筛子，并解决了Project Euler问题10。
sieve :: [Integer] -> [Integer]
sieve (0 : xs) = sieve xs
sieve (n : xs) = n : sieve (mark xs 1 n)
where
mark :: [Integer] -> Integer -> Integer -> [Integer]
mark (y:ys) k m | k == m = 0 : (mark ys 1
浏览 3提问于2012-07-30得票数 11
回答已采纳
3回答
我需要按升序找到一定数量的素数，从2开始。我有一个工作算法，它以一个数-极限为参数，它找到所有小于这个极限的素数。
例如，对于param 20，它将返回2,3,5,7,11,13,17,19，但我需要输入5并获取2,3,5,7,11。最好的方法是什么？我正在使用Eratosthenes的筛子，没有办法限制这个数字--删除部分，因为我不知道第195个素数有多大，因此我不知道是否应该删除1568年或1268426的所有2的倍数。我希望问题是清楚的，谢谢你的帮助
浏览 0提问于2012-01-29得票数 1
回答已采纳
4回答
我必须在两个给定的数字a和b之间找到质数，这两个数字的范围都在1和10^12之间。为了做到这一点，我正在使用Eratosthenes筛子。我怎么才能得到这么大的数组呢？如果超过大小10^6，则会出现错误。
浏览 0提问于2016-03-10得票数 0
我正在尝试实现一种在给定范围内生成随机素数的方法。
我试着用一种简单的方法来判断一个数字是否是素数，高级的简单方法，Wilson的方法和我的方法，只要我基于这个算法的代码比以前所有的方法都快，我就能找到一个数是否是素数。
虽然效率是令人满意的，但我知道有一个实现可以在不创建数组的情况下工作，并且代码运行得更快，但是我不知道如何做到这一点，所以我的问题是显而易见的。
import acm.program.*;
import acm.util.RandomGenerator;
public class exercise4 extends Program {
public int nextPrim
浏览 0提问于2018-01-15得票数 5
回答已采纳
我试图在一定范围内打印出素数，并决定与Eratosthenes的分段筛子一起，找到从2到sqrt(n)的素数，并使用列表中找到的素数从任何范围打印出素数，这样范围内的数字不能被筛子列表中的任何一个数除以，最后是素数。
我的代码适用于小范围，如从2到10和3到5，但开始打印出副本和大n的非素数。有什么帮助吗？
from math import sqrt, ceil
#Creating segmented sieve
start=2
stop=1000000000
sieve=[i for i in range(2,ceil(sqrt(stop)+1))]
浏览 3提问于2020-06-20得票数 0
回答已采纳
1回答
我当时正在解决欧拉项目的第70号问题，而我的欧拉函数速度很慢。有人能帮忙吗？
欧拉项目问题70描述：
Euler's Totient函数φ( n )有时称为phi函数，用来确定相对于n素数小于或等于n的正数数，例如，当1，2，4，5，7和8都小于9，相对于9，φ(9)=6，因此φ(1)=1.
有趣的是，φ( 87109 )= 79180，可以看出87109是79180的置换。
求n，1<n<N的值，其中φ(n)是n的置换，且n/φ(n)的比值最小。
输入格式：包含整数N
约束： 1<=N<=10**7
输出格式：打印与测试用例对应的答案
示例输入： 100
示例
浏览 5提问于2022-08-05得票数 0
1回答
关于伊拉托斯提尼筛的几个问题
、、、、
我学到了“使用C++的编程原则和实践”，当时我正在做一个涉及Eratosthenes筛子的早期问题，而且我有意想不到的输出，但我不能确切地确定问题是什么。这是我的代码：
#include <iostream>
#include <vector>
int main()
{
std::vector<int> prime;
std::vector<int> nonPrime;
int multiple = 0;
for(int i = 2; i < 101; i++) //initialized to fir
浏览 0提问于2018-03-12得票数 2
回答已采纳
3回答
给定一个整数数组，如何返回一个包含所有素数的降序数组？ def returnPrime (list): 示例:如下所示调用函数时： returnPrime ((10,21,3,8,9,11,44,62,100,19)) 它应该会返回 [19,11,3]
浏览 14提问于2021-01-03得票数 0
我花了将近3天的时间来解决问题。
我想做一个Scala函数式解决方案(意思是"no var"，"no mutable data")，但每次都超过了时间限制。
我的解决方案是：
object Main {
def sqrt(num: Int) = math.sqrt(num).toInt
def isPrime(num: Int): Boolean = {
val end = sqrt(num)
def isPrimeHelper(current: Int): Boolean = {
if (current > end
浏览 0提问于2014-05-29得票数 0
我有两个埃拉托斯提尼筛子的实现。这是第一个：
public class SieveOfEratosthenes extends PrimeGenerator {
private boolean[] sieve;
private List<Integer> primes;
public SieveOfEratosthenes(int depth) {
super(depth);
sieve = new boolean[depth + 1];
primes = new ArrayList<>();
浏览 2提问于2015-03-09得票数 2
回答已采纳
我已经在c++中实现了Eratosthenes的筛子，但是代码在输入大于10^10的时候崩溃了。编译器显示信号11(SIGSEV)。因为全局数组bool a[5000000000000000];.To校验奇数高达10^16，我把数组大小取为(10^16)/2 =5* 10^15。如何减少空间？有一个问题的答案，我尝试了相应的，但我的程序crashes.Could任何人提供实现细节来解决它？
#include <bits/stdc++.h>
using namespace std;
long long unsigned n,sqN;
bool a[5000000000000000]
浏览 1提问于2016-08-30得票数 1
我想知道，我是否能得到一些反馈，以实现我的“埃拉托斯提尼筛”和孪生质数。我跟踪了这个伪码。
很少有人注意到：
我添加了MAX(primes.size << 1, (x << 1) + 1)，使我调整表的大小，使之足够大，以找到下一个孪生素数。
使用结构跟踪动态数组的大小。
我所关心的事情：
使用POW
goto语句
只有操场可以测试代码：https://www.onlinegdb.com/HydogHGxw
谢谢。
#include "prime.h"
#include <math.h>
#include <stdbool.h>
浏览 0提问于2020-07-19得票数 4
回答已采纳
1回答
用Python编写素数函数的更有效的方法是什么？下面是我学习Python时的版本：
def print_prime(max):
i = 1
while i < max:
is_odd = True
for nd in range(2, i):
if nd < i and i % nd == 0:
is_odd = False
break
if(is_odd):
print(i)
i += 1
print_prime(100)
浏览 3提问于2022-05-04得票数 0
3回答
我用python编写了两个原始性测试。第一种是基于审判分工，第二种是使用埃拉托斯提尼的筛子。我的理解是，筛子的时间复杂度应该比试用期小，所以筛子应该更快。
然而，当我运行它时，审判部门要快得多。例如，当n = 6*(10**11)时，is_prime(n)所花费的时间不到1秒钟，但是is_prime_sieve(n)实际上永远不会结束！我把筛子写错了吗？
我的代码是：
# determines if prime using trial division
def is_prime(n):
d = {}
u = math.floor(math.sqrt(n))
i = 2
浏览 6提问于2015-06-05得票数 2
回答已采纳
2回答
我必须找到给定数字N的因子总数，这里可以大到10^14，.I尝试计算素数直到10^7，然后使用素数factors.However的指数来找到因子，结果太慢了，因为使用筛子找到素数需要0.03秒。我如何更快地计算因子总数，如果可能的话，不计算素数？请伪代码/well解释算法将非常感谢。
浏览 3提问于2012-09-06得票数 4
当我提交解决方案时，我得到了time limit exceeded错误。
<?php
$stdin = fopen('php://stdin', 'r');
$testcase = fgets($stdin);
$n=1;
while($n<=$testcase){
$start = fgets($stdin);
$end=fgets($stdin);
if($start==1) {
$start=2;
}
for($i=$start;$i<$end;$i++){
$
浏览 2提问于2016-02-12得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
