首页 文章
  • 0 votes
     answers
     views

    使用向量用C求解Eratosthenes的Sieve并收到异常的错误信息

    在今天,我问了一个关于用2D阵列实现Eratosthenes筛子的问题,并且有几个人告诉我使用向量代替 . 唯一的问题是我不知道如何在C中使用向量 . 我今天使用向量而不是2D数组重写了我的程序,直到程序结束时我才收到以下错误: sieve.h:在函数'void printPrimes(std :: vector *,int)':sieve.h:42:20:error:'std :: cout ...
  • -4 votes
     answers
     views

    具有[保持]功能的素数

    如何使用函数找到素数?我试试这个: int primeNumbers(num) { for (int i = 2; i <= num; i++) { for (int j = 2; j < i; j++) { if (i % j == 0) { continue; } else ...
  • -1 votes
     answers
     views

    欧拉的功能

    “产品在不同的素数上划分n . (符号在文章Arithmetical函数中描述 . )” 根据维基百科,这是欧拉的功能 . 如果n是素数怎么办?这个函数会返回(n-1),不是吗?但那不是不正确的?
  • 121 votes
     answers
     views

    如何确定一个数字是否是正则表达式的素数?

    我在RosettaCode上找到了以下Java代码示例: public static boolean prime(int n) { return !new String(new char[n]).matches(".?|(..+?)\\1+"); } 我特别不了解Java,但除了正则表达式本身之外,还要理解这个片段的所有方面 当你在内置的PHP函数中找到它时,我有...
  • 7 votes
     answers
     views

    在数据库中存储大质数

    这个问题让我觉得有些奇怪 . 我很好奇你如何能够代表数据库中的素数列表 . 我不知道单个数据类型是否能够精确且一致地存储大量素数 . 我担心的是,当素数开始包含1000个数字时,从数据库中引用可能有点困难 . 有没有办法在DB中表示大量素数?我很确定这个主题已经接近过了 . 关于这个问题的一个问题是,质数不能分解为因素 . 如果他们能解决这个问题就容易多了 .
  • 6 votes
     answers
     views

    得到所有除数的最有效方法[重复]

    可能重复:有效地查找数字的所有除数 这更像是一个效率问题,而不是通用的“找到一种方法”,但在得到一些奇怪的结果后,我想看看是否有人可以告诉我为什么最后一种方式如此低效: 方式1:蛮力,没有优化 public static List<int> proper_divisors(int x) { List<int> toreturn = new Lis...
  • 1 votes
     answers
     views

    一个数字的不同素数因子的数量

    问:给定A,B和K.找到具有K DISTINCT素因子的A和B(包括)之间的所有数字 . 这就是我所做的 . 我已经实施了Eratosthenes的Sieve并计算了所有素数直到A,B的上界 . 然后我继续找到这些素数中的哪一个是A和B之间数字的因子 . 如果不同质数的数量等于K,我增加计数 . 我遇到的问题是时间问题 . 即使在实施筛子后,计算答案为2,10000,1(2到100000之间的数字...
  • 1 votes
     answers
     views

    具有与质数数量成比例的数据的主筛的空间复杂性是多少?

    我正在练习编写针对空间或时间复杂度优化的算法 . 使用优质筛,至少您必须存储所有找到的素数列表 . 似乎与发现的素数成比例的数据是这种算法可能使用的最小空间量 . 这个理由有效吗? 如何评估此算法的空间复杂度? From Wikipedia about the sieve of Atkin - 我不确定的是,当素数超过此值时,筛子如何使用O(n ^ 1/2)空间 . 这就是为什么它似...
  • 2 votes
     answers
     views

    鉴于其素数因子分解,生成一个数的所有除数

    我想找到范围[1,107]中所有数字的除数 . 我知道它可以在O(sqrt(n))中解决 . 但是在此之前必须运行Eratosthenes的筛子,这可以很容易地修改以获得一个数字的素数因子化(通过跟踪每个数字的一个主要因素) . 所以我想知道使用其素数因子分解生成所有因子会更有效吗?设n = p1k1 * p2k2 * .... * pmkm 我认为这种符号可以在筛子后在O(mΣki)中获得 .经...
  • 2 votes
     answers
     views

    找到与给定值相加的最小素数

    我想找到总和给定值的最小素数集,例如9 = 7 2(不是3 3 3) . 我已经使用sieve of eratosthens生成了一个素数数组 我按降序遍历数组,以获得小于或等于给定数字的数组最大素数 . 如果数字是奇数,这很好用 . 但是对于偶数而言则失败,例如122 = 113 7 2但122 = 109 13 . 从Golbach's Conjecture我们知道任何偶数都可以表示为两个素数...
  • 118 votes
     answers
     views

    检查数字是否为素数的最佳算法是什么?

    只是我正在寻找的一个例子:我可以用一点代表每个奇数对于给定的数字范围(1,10),从3开始: 1110 以下字典可以挤得更对吗?我可以通过一些工作来消除五的倍数,但是以1,3或7或9结尾的数字必须存在于位数组中 . 希望这能澄清我想要的东西 . 我正在寻找最好的算法,检查数字是否为素数,即布尔函数: bool isprime(number); 我想知道实现此功能的最佳算法 . 当然,我可以查询...
  • 5 votes
     answers
     views

    编程以查找非常大的给定整数范围内的所有素数

    我在一个编程网站上遇到了以下这个问题:Peter希望为他的密码系统生成一些素数 . 帮助他!您的任务是生成两个给定数字之间的所有素数! 输入 输入以单行中的测试用例数t开始(t <= 10) . 在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n <= 1000000000,n-m <= 100000) . 我提出了以下解决方案: imp...
  • 2 votes
     answers
     views

    Prime Generator算法

    我一直在努力解决素数生成器算法的SPOJ问题 . 这是问题所在 彼得想为他的密码系统生成一些素数 . 帮助他!您的任务是生成两个给定数字之间的所有素数!输入输入以单行中的测试用例数t开始(t <= 10) . 在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n <= 1000000000,n-m <= 100000) . 输出对于每个测...
  • -1 votes
     answers
     views

    Erastothenes C SPOJ的分段筛[重复]

    这个问题在这里已有答案: Segmented Sieve of Eratosthenes? 5个答案 Efficient algorithm to get primes between two large numbers 10个答案 我知道之前已经问过这个问题,但是我无法完全理解如何实现Eratosthenes的分段筛 . Problem 输入以单行中的测试用例数t开始(t <=...
  • -5 votes
     answers
     views

    计算两个数字之间的Primes的程序 - SPOJ问题2

    这是参考SPOJ问题2 - http://www.spoj.com/problems/PRIME1/ 我在这里引用它 - Problem :彼得想为他的密码系统生成一些素数 . 帮助他!您的任务是生成两个给定数字之间的所有素数! 输入 输入以单行中的测试用例数t开始(t <= 10) . 在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n &lt...
  • -1 votes
     answers
     views

    SPOJ PRIME1 Prime Generator:错误答案?

    在SPOJ上做this question,尝试使用筛子和分段筛子来获得所需的质数 . 我的代码如下: //Prime Generator #include <iostream> #include <math.h> #include <cstdio> using namespace std; int main() { //traditional si...
  • 2 votes
     answers
     views

    SPOJ上的素数区间(PRINT)

    我实施了一个筛子,用于在给定范围之间找到素数,首先找到最高可能数的平方根的上限,然后为每个测试用例找到素数达到所需的限制 . 我从每个素数的平方开始标记复合 . 这在SPOJ PRIME1(http://www.spoj.com/problems/PRIME1/)中以0.07获得AC,但获得PRIME INTERVAL-PRINT的TLE . (http://www.spoj.com/probl...
  • -1 votes
     answers
     views

    代码优化 - 生成素数

    我正在尝试编写以下问题的代码: 输入 输入以单行中的测试用例数t开始(t <= 10) . 在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n <= 1000000000,n-m <= 100000) . 产量 对于每个测试用例,打印所有质数p,使得m <= p <= n,每行一个数,由空行分隔的测试用例 . 样本输入: 2 ...
  • 0 votes
     answers
     views

    Miller-Rabin素性测试给出了错误的答案

    我正在尝试制作RSA算法 . 为此,我需要rabin-miller见证模幂运算(至少我需要使用它) . 当我生成随机数来检查rabin miller它们是否为素数时问题就出现了,结果是非素数是rabin-miller算法的主要数字 . 有人可以帮我看看我失败的地方 . 提前致谢 . int mod_exp(int a, int b, int n){ int d = 1,i,j=0; ...
  • 0 votes
     answers
     views

    SPOJ Prime发电机错误答案

    这是问题的链接 - :http://www.spoj.com/problems/PRIME1/ . 该问题要求在给定的范围 1 <= m <= n <= 1000000000 , n-m<=100000 之间找到所有素数 . 我已经实现了Segmented Sieve这里是逻辑 - :因为问题的最大值为10 ^ 9,所以我会找到所有带有square_root(10 ^ 9)...
  • -1 votes
     answers
     views

    SPOJ上的Prime Generator PRIME1

    彼得想为他的密码系统生成一些素数 . 帮助他!您的任务是生成两个给定数字之间的所有素数!输入 输入以单行中的测试用例数t开始(t <= 10) . 在接下来的t行中的每一行中,存在由空格分隔的两个数m和n(1 <= m <= n <= 1000000000,n-m <= 100000) . 产量 对于每个测试用例,打印所有质数p,使得m <= p <= n...
  • 118 votes
     answers
     views

    检查数字是否为素数的最佳算法是什么?

    只是我正在寻找的一个例子:我可以用一点代表每个奇数对于给定的数字范围(1,10),从3开始: 1110 以下字典可以挤得更对吗?我可以通过一些工作来消除五的倍数,但是以1,3或7或9结尾的数字必须存在于位数组中 . 希望这能澄清我想要的东西 . 我正在寻找最好的算法,检查数字是否为素数,即布尔函数: bool isprime(number); 我想知道实现此功能的最佳算法 . 当然,我可以查询...
  • 15 votes
     answers
     views

    这个正则表达式如何工作?

    从this article, /^1?$|^(11+?)\1+$/ 检查一个数字(它在一元中的值)是否为素数 . 使用它, perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;' 返回素数列表 . 我没有足够的Perl经验,但据我所知,正则表达式将是 true ,对于不是素数的数字 . 因此,如果我们使用此表...
  • 7 votes
     answers
     views

    python中的Primality测试[重复]

    这个问题在这里已有答案: What is the best algorithm for checking if a number is prime? 23个答案 我正在尝试在Python中进行简单的素性测试 . 根据维基百科,primality test如下: 给定输入数n,检查从2到n - 1的任何整数m是否除以n . 如果n可以被任何m整除,则n是复合的,否则它是素数 . 我开始排...
  • 1 votes
     answers
     views

    Java中的模幂运算使用eulers totient和中国余数定理[关闭]

    编辑 - 澄清 我正在尝试使用lagrange和中文余数定理在Java中实现模幂运算 . 例如,如果N是55,已经给出了素数因子5和11,则phi是40,所以我知道在N低于55时有40个数字共同素数 . 我的导师说这样做的方法是“使用拉格朗日定理” ,以5和11为模的几次乘法和CRT结合两种结果“ 我的问题是如何计算这些数字?我需要他们把它们放入一个中国余数定理来完成计算,但我想不出一个聪明的方法...
  • 11 votes
     answers
     views

    函数is_prime - 错误

    这是来自codeacademy.com的问题,我正在学习Python . 所以我想要的是定义一个函数,检查一个数字是否为素数 . 如果是,则返回True . 如果不是,则返回False . 这是我的代码: def is_prime(x): lst = [] # empty list to put strings 'False' and 'True' for i in ...
  • 0 votes
     answers
     views

    确定Ruby中的数字是否为素数

    我正在尝试编写一个方法,根据被评估的整数是否为素数返回true或false . 下面的代码是基于阅读维基百科文章,以前的stackoverflow答案等拼凑在一起的东西 . 目前程序对素数返回true,但不返回false . 我想在不使用任何内置函数的情况下执行此操作 . 我该怎么解决这个问题? def prime?(integer) (2..integer - 1).each do |x| ...
  • 0 votes
     answers
     views

    欧拉在C中的赋形函数

    对于自然数n,Euler的totient函数被定义为集合 {1,...n} 中与 n 相对素数的自然数 . 我必须用C语言编写一个程序,这样输入 n 的输出就是 n 的Euler的整数函数 . 这是我的尝试: #include<stdio.h> int main(void) { int n,k; scanf("%d", &n); for (k=1; ...
  • 21 votes
     answers
     views

    有效存储素数

    对于一个库,我需要将第一个素数存储到一个极限L.这个集合必须有一个O(1)查询时间(检查一个数字是否为素数)并且它必须很容易,给定一个数字,找到下一个素数(假设它小于L) . 鉴于L是固定的,产生清单的Eratostene筛子是好的 . 现在,我使用一个打包的布尔数组来存储列表,该列表仅包含3到L(含)之间的奇数的条目 . 这需要(L-2)/ 2位内存 . 我希望能够在不使用更多内存的情况下静态增...
  • 321 votes
     answers
     views

    列出N以下所有素数的最快方法

    这是我能提出的最佳算法 . def get_primes(n): numbers = set(range(n, 1, -1)) primes = [] while numbers: p = numbers.pop() primes.append(p) numbers.difference_update(set(range(p*...

热门问题