26回答
计算一个数的最大素因数的最佳方法是什么？ 我认为最有效的方法是： 找出整除的最小质数 检查除法结果是否为质数 如果不是，找到下一个最低的 转到2。 我把这个假设建立在更容易计算小素数因子的基础上。这是正确的吗？我还应该研究哪些其他方法？ 编辑:我现在已经意识到，如果有超过2个素数因子在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2失败了，因此需要一个递归算法。 再次编辑:现在我意识到这仍然有效，因为最后找到的质数必须是最高的，因此对步骤2的非质数结果的任何进一步测试都将导致较小的质数。
浏览 361提问于2008-08-22得票数 194
回答已采纳
1回答
我试图实现一个有效的算法，它可以找到给定数n的素数因式分解，我也有至少n个素数的列表。
一个例子:如果我有一个数字n= 50，结果应该是: 2，5，5。
到目前为止，我的想法：
检查n == 1，如果真返回1检查n == 2，如果真返回2
如果1和2都是假的：
results.Find 尽可能经常地将n除以2，并在结果向量中添加2，试图在素数列表中找到(可能被2除)n。如果n在列表中，则将其添加到结果中，并返回列表中的最大素数，即小于n。除以在步骤6中找到的素数。如果有可能除以没有rest的除法，将质数添加到results.Check if n==1并返回结果(如果为)，重复步骤5-9.
这个
浏览 2提问于2020-03-17得票数 0
4回答
我在试着做一个素数列表。我已经对它进行了编码，但它只告诉我1 - 100的质数是1。我不确定为什么会发生这种情况。我也想为它做一个JFrame。
import javax.swing.JOptionPane;
public class ProgrammingAssignment7 {
public static void main(String[] args) {
//Scanner Scan = new Scanner (System.in);
//DECLARE VARIABLES
int x = 1;
int i
浏览 1提问于2013-04-08得票数 0
3回答
我正在做项目Euler #7，我写了：
public class Seven {
public static void main(String[] args) {
int i = 0;
int c = 1;
while (c <= 10001) {
if (squareRootIsPrime(i)) {
c++;
}
i++;
}
System.out.println(Math.sqr
浏览 4提问于2017-08-01得票数 0
我正在写一个打印给定长度的素数集的应用程序。这是一个一般长度的应用程序，例如从1到100的所有数字
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class Sieve
{
private int number;
public Sieve (int maxPrime)
{
number = maxPrime;
}
public Set<Integer> getPrimes()
{
浏览 0提问于2012-04-05得票数 0
1回答
我已经搜索了所有我能想到的站点，但无法确定ruby1.8在mathn下的Prime类中创建质数列表所使用的基本算法。下面是succ方法的一个可运行版本，调用100次(为了找到第100个质数)。有人知道这是怎么回事吗？
number_of_primes = 100
seed = 1
primes = Array.new
counts = Array.new
while primes.size < number_of_primes
i = -1
size = primes.size
while i < size
if i == -1
seed +=
浏览 0提问于2012-12-08得票数 4
回答已采纳
1回答
我知道这个问题在这个论坛上已经被问了好几次了。但我仍然在发帖，因为没有一个答案看起来很具体。专家们，您能告诉我什么时候使用迭代器吗？当我们有一个非常大的数据集时，我们是理想地使用它，还是当我们有大量数据要返回时，我们将它用作方法的返回类型？
浏览 27提问于2018-08-10得票数 -6
9回答
我有一段检查给定数字是否为质数的代码：
If x Mod 2 = 0 Then
Return False
End If
For i = 3 To x / 2 + 1 Step 2
If x Mod i = 0 Then
Return False
End If
Next
Return True
我只对numbers 1E7 <= x <= 2E7使用它。然而，它非常慢-我几乎不能一秒检查300个号码，所以检查所有的x需要超过23天的时间……
有没有人能给我一些改进的建议，或者说一下我可能会以这种方式重复做些什么？
浏览 2提问于2011-02-13得票数 3
回答已采纳
在许多编程问题(例如，一些Project Euler问题)中，我们被要求将答案报告为答案除以1,000,000,007后的余数。
为什么不是其他的数字呢？
编辑:两年后，我知道的是:这个数字是一个大素数，对于这样一个问题，任何答案都是如此之大，以至于报告余数是有意义的(因为对于原生数据类型来说，这个数字可能太大了)。
浏览 1提问于2012-09-25得票数 21
我正在尝试使用pthread的数据并行方法来实现Eratosthenes问题的筛子，但是我不能弄清楚当发现"2“是一个质数时，thread-1是如何广播给所有其他线程的，当所有其他线程标记为2的倍数时，它们应该再次等待下一个质数。如何实现线程的多重等待？
浏览 0提问于2010-09-26得票数 1
2回答
我是Ruby的新手，我认为这是通过解决Project Euler的问题来学习更多东西的一个很好的方法。
以下是我对问题5使用暴力的想法：
#What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
end_point = 1_000_000_000
start_point = 2_520
(start_point..end_point).each do |number|
flag = true
(2..20).each do |divisor|
浏览 0提问于2011-06-14得票数 0
回答已采纳
4回答
所以，我想找出600851475143的最大素因数。我有一个简单的方法可以找到当前最大的一个，它是这样的：
private static void findPrimeFactors(long num) {
ArrayList<Long> list = new ArrayList<Long>();
for (long i = 1; i <= num; i++) {
int lol = 0;
for (int a = 1; a < i; a++) {
浏览 0提问于2014-02-02得票数 0
1回答
这个函数的时间复杂度是多少？
bool prime(int n) {
if(n <= 1) {
return false;
} else if(n <= 3) {
return true;
} else if(n % 2 == 0 || n % 3 == 0) {
return false;
} else {
for(int i = 5; i * i <= n; i += 6) {
if(n % i == 0 || n % (i + 2) == 0) {
浏览 4提问于2020-07-14得票数 2
public class Prime
{
public static void main(String args[]){
int i,m=0,flag=0;
int n=3;//it is the number to be checked
m=n/2;
if(n==0||n==1){
System.out.print(n+" is not prime number");
}
else
{
for(i=2;i<=m;i++)//Why are we using m here
浏览 27提问于2019-07-23得票数 0
假设你有10e4个数字。每个数字不超过10e6。如果每个数字可以表示为两个素数的倍数，那么如何有效地检查每个数字？ 例如: 15可以表示为3 *5.6。6可以表示为2*3。但8不能由两个素数表示。
浏览 54提问于2021-09-28得票数 0
2回答
有没有合适的算法，允许程序在一个未排序的矩阵中搜索最大的质数。该矩阵的大小为m*n，并且可以用其他素数和非素数填充。搜索必须找到最大的素数。
我已经研究了分治算法、二叉树和分步搜索，但所有这些都是处理排序矩阵的。
浏览 0提问于2015-07-08得票数 1
素数生成器需要介于某个范围之间的质数。
输入:输入以一行中的测试用例数t开始(t<=10)。在接下来的每一条t行中，有两个数字m和n (1 <= m <= n <= 1000000000，n-m<=100000)由空格分隔。
输出:对于每个测试用例，打印所有质数p，使得m <= p <= n，每行一个数字，测试用例由空行分隔。
我的程序可以很好地运行这个解决方案，但是超过了时间限制，并且它不被接受为一个解决方案。
我已经用scanf和printf替换了cin和cout。我已经将for循环替换为while循环等等。我还可以采取哪些其他措施来加速我的解决方
浏览 0提问于2019-03-22得票数 1
1回答
我被一个java项目卡住了，我需要将玩家的总数分成最优的组。我有两个常量可以帮助我做到这一点(MAX_POOL_SIZE和MIN_POOL_SIZE)。
例如，如果玩家总数是20，那么最优的组大小应该是4x5，而不是3x6+2(使用MAX_POOL_SIZE=6)。如果我有9个玩家，最佳数量应该是3x3，具有相同的MAX_POOL_SIZE。
这里最大的困难(对我来说)是当玩家的总数是一个质数时。
浏览 0提问于2013-04-21得票数 0
回答已采纳
为什么这个算法具有指数时间复杂度？
我知道"Modulus“是一个按位运算的运算符，对单个位进行运算。因此，在最坏的情况下，我们需要执行sqrt(2^n)除法。这是一种exp时间算法。
如果这是真的，那么所有的算法不会变成指数时间吗？请解释一下。
Find-Factor(X)
1: if X is even then
2: return ”2 is a factor”
3: end if
4: for i = 3 to Sqrt(X) by +2 do
5: test if X%i = 0, if yes, output ”i is a factor”
6: end for
7
浏览 1提问于2014-09-02得票数 1
我有在CodeEval上得到主回文问题的正确解决方案，但仍然得到以下错误：
TypeError: path must be a string
以下是我的解决方案：
var fs = require('fs');
fs.readFileSync(process.argv[2])
.toString()
.split('\n')
.forEach(isPrime)
function isPrime(input){
if (input === '') return;
if (input < 1001 ) {
va
浏览 1提问于2016-05-28得票数 0
我们如何在这段代码中使用sqrt(n)而不是n/2？使用sqrt(n)是否正确
static boolean isPrime(long n)
{
if(n<=1) return false;
double limit = Math.sqrt(n);
for(long i = 2; i <= limit; i++)
{
if(n%i==0) return false;
}
return true;
}
浏览 0提问于2014-01-27得票数 0
我调试了我的代码，一切都很完美。但出于某种原因，我的代码从来不写到控制台。
这是我的代码：
long largest = 0;
for (long i = 1; i < 600851475144; i++)
{
long check = 0;
for (long j = 1; j < i + 1; j++)
{
if ((i%j) == 0)
{
check++;
浏览 2提问于2016-10-22得票数 1
回答已采纳
1回答
这个程序生成质数。它工作得很好，但我想加快速度，因为它需要相当长的时间来生成所有的质数
#!/usr/bin/python
#intgr = int(raw_input ("Please enter your number: "))
intgr = 50000
for i in range (2, intgr+1):
j = 2
while j<i:
if (i%j) == 0:
break
j += 1
if j == i:
#print "prime",
浏览 1提问于2019-04-05得票数 0
import java.util.Scanner;
public class forLoopPrimeNumberSearch {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter begining value: ");
int beginingValue = input.nextInt();
System.out.print("Ent
浏览 18提问于2020-07-17得票数 0
1回答
isPrime::Integer->Bool
isPrime n=not (hasfactor n 2(div n 2))
hasfactor::Integer->Integer->Integer->Bool
hasfactor n low high
|low>high=False
|mod n low==0=True
|otherwise = hasfactor n (low+1) high
我理解大部分代码，除了第二行，not (hasfactor n 2(div n 2))。为什么更高的界限是(div n 2)？假设我们使用test
浏览 1提问于2017-04-23得票数 0
4回答
我正在尝试创建一个用于素数分解的pascal程序，即
16 = 2*2*2*2
210 = 2*3*5*7
我应该输入一个数字，然后返回素数分解。我不理解数学意义上的解决方案，有人能给我解释一下这个算法或伪代码吗，只要我明白我创建的编程并不是一个真正的问题。
谢谢
浏览 0提问于2011-10-13得票数 3
1回答
我想弄清楚这段代码的大O复杂度： prime_factorize(N) {
for (int i = 2; i <= N; i++) {
while (N % i == 0) {
print i
N = N / i
}
}
} 这实际上不是一种编程语言--它只是伪代码。 我知道伪代码在做什么。我也知道代码可以优化为只到sqrt(N)，但我想在发布代码时弄清楚代码的运行时。 虽然很容易说运行时是二次的，但我非常确定这是错误的。我之所以认为它是错误的，是因为我知道质数筛分算法是在O(nloglogn)
浏览 17提问于2020-02-01得票数 0
回答已采纳
我已经学习了公钥加密的理论，但我错过了与物理世界的联系。例如：
有人告诉我，好的RSA加密应该依赖于300位十进制数字的质数，但为什么呢？这个数字是谁想出来的？破解这种加密需要多长时间(不同机器的统计数据)。
我试过谷歌，但找不到我想要的东西。有没有人？
谢谢
浏览 0提问于2012-08-07得票数 12
回答已采纳
bool is_prime(BigInt num)
{
if(num == 0 || num == 1 || (num != 2 && num % 2 == 0))
return false;
BigInt sq = sqrt(num);
for(BigInt i = 3; i <= sq; ++i, ++i)
if(num % i == 0)
return false;
return true;
}
我们只需要检查到平方根。证明->
浏览 1提问于2020-11-02得票数 0
出于测试目的，我需要找到两个64位整数值，这两个值与具有特定位模式的128位中间值完全相乘。显然，我可以生成所需的中间值并除以随机值，直到我找到一个有效的组合，但是有没有更有效的方法呢？
浏览 7提问于2009-09-16得票数 3
回答已采纳
//获取2到给定范围内的质数//当内部for循环运行2号时，它将9打印为质数。
import java.util.*;
import java.io.*;
class A
{
public static void main(String args[])
{
System.out.println("Enter the number till which the prime number is to be printed:");
Scanner sc = new Scanner(System.in);
int limit = sc.nextInt();
浏览 0提问于2014-03-17得票数 0
我已经开发了一个算法来寻找给定数字的因子。因此，它还有助于确定给定的数字是否为质数。我觉得这是寻找因子或质数的最快算法。
该算法确定给定的数字在5*N (其中N是输入数字)的时间范围内是否为质数。所以我希望我可以称之为线性时间算法。
如何验证这是否是可用的最快算法？在这件事上有人能帮上忙吗？(比GNFS和其他已知文件系统更快)
算法如下所示
Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it
浏览 0提问于2011-04-07得票数 8
回答已采纳
3回答
RSA和素数生成器算法
、、、
好吧，我对RSA的数学工作原理的理解可能还不够深入，所以如果这是愚蠢的，请随时扇我耳光：
为了生成私钥，我们需要两个随机的大素数。没有算法可以精确而有效地做到这一点，但有一些算法可以生成具有99.99999...(数量级为9)的素数的...999%概率的大数。
我的问题是:如果在生成密钥时，由于运气不佳，素数生成算法生成了一个非素数，会发生什么？这对使用这个不吉利密钥的软件有什么影响？
编辑:我知道其他因素更有可能是这件事上糟糕结果的来源；这只是纯粹的书呆子数学好奇心。
浏览 7提问于2010-11-12得票数 12
回答已采纳
我理解了Eratosthenes clearly.But的筛子我在理解分段sieve.My时遇到了麻烦问题是给定两个范围
(a=b=10^8)
如何找到这两个区间之间的质数，其中
b-a<=10^5)
请帮我设计代码。
浏览 0提问于2018-09-27得票数 1
我是一个java的初学者，不能理解"count“在这个程序中的用法。我必须在用户输入的某个范围内打印质数。
import java.util.Scanner;
public class JavaProgram
{
public static void main(String args[])
{
int start, end, i, j, count=0;
Scanner scan = new Scanner(System.in);
System.out.print("Enter the Range :\n&
浏览 2提问于2018-02-07得票数 0
3回答
标题几乎说明了一切，但我将举例说明这一点:假设您有一个字符数组a，另一个也是字符数组b。有没有更好的方法只放入位于b中质数位置的char？假设我们有一个具有质数位置的数组。现在，我天真的代码看起来像这样。
for(i = 0; i < n; i++)
a[i] = b[j + prime[i]];
这里primei存储了b的素数位置，并且b比a大得多，j是b中的任意位置(不会有越界问题，因为j+primei不会超过b的边界)。
浏览 0提问于2013-04-04得票数 0
2回答
对于线性探测，步长几乎总是1，但可以使用其他步长，只要步长相对于表大小是质数，以便最终访问每个索引。如果不满足此限制，则可能无法访问所有索引...(基本问题是:您需要访问数组中的每个索引，从任意索引开始，向前跳过固定数量的索引，跳到下一个索引，如果需要的话，使用模数包到数组的开头。)
我不明白为什么如果步长不是表大小的质数，那么为什么不能访问所有的索引，我也不明白为什么相反的情况是正确的:如果步长相对于数组的大小是相对质数的，那么所有的索引都会被访问。
我在几个手工设计的例子中观察到了这个相对重要的属性，但我不明白为什么它在每种情况下都有效。
简而言之，我的问题是:为什么访问数组的每个索引的步
浏览 2提问于2015-03-27得票数 0
1回答
搜索python质数生成器，我发现：
def primes(n):
if n==2: return [2]
elif n<2: return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
浏览 10提问于2013-07-01得票数 4
回答已采纳
6回答
一个简单的问题:当你必须定义一些数组在C中可以接受的(任意)最大值时，人们的做法是什么?因此，一些人只是选择一个整数，希望它足够大，另一些人选择接近整数的质数(!)，等等，还有一些更深奥的数字，比如接近的质数……诸若此类。
那么，我想知道决定这些值的一些最佳实践是什么？
谢谢。
浏览 0提问于2010-09-18得票数 0
回答已采纳
4回答
我必须得到一个素数序列。但是我的代码不能工作。怎么可能修复它呢？
var num1 = parseInt(prompt('Enter a number'));
var num2 = parseInt(prompt('Enter a number'));
var num3 = 0;
function primeSeq(num1, num2) {
var b = 1;
var c = '';
if (num1 > num2) {
num3 = num2;
num2 = num1;
num1 = num3;
}
for (va
浏览 0提问于2016-11-07得票数 0
2回答
我有一个数字x，我想找出所有对它来说是质数的数字。
到目前为止我的代码如下：
For i = 1 To x-1
if [number n is relatively prime to x] Then
ListBox1.Items.Add(x)
End If
Next
提前感谢
浏览 0提问于2012-03-02得票数 0
回答已采纳
5回答
我想让我的程序找到数字600851475143的最大素因数。例如，13195的素数因子是5、7、13和29，其中29是最大的。虽然我的代码确实可以工作，但即使对于小得多的输入，例如6kk (大约需要15秒)，答案也需要太长时间才能出现。对于12kk，它需要37秒，所以增量甚至比线性更差)，它比我应该用作输入的数字小100k倍。下面是我的代码，任何关于提高代码效率的帮助都将不胜感激。
#include <stdio.h>
#include <math.h>
int main()
{
long long int number=600851475143;
i
浏览 0提问于2016-12-06得票数 0
1回答
数值误差
、、
我写了一个快速筛子来测试一个数字是否是质数。我有两个问题：
1)我测试了一个200位的质数，它错误地说它不是质数。我相信这是由于浮点错误(或类似的错误)。我如何才能使这一点更准确？
2)有没有更好的方式来写这篇文章？我使用了decimal来处理更大的数字。这是最好的方法吗？
import math
from decimal import *
def isprime(n):
i = 2
a = 1
if n == 1:
return 0
if n == 2 or n == 3:
return 1
while i < n
浏览 1提问于2016-04-06得票数 1
3回答
我对Fortran非常陌生，两天前就开始学习它了。我开始学习Fortran是因为我正在学习质数，我用python写了一个程序，速度非常快，它可以在0.1秒内确定123098237是一个质数。印象深刻，我知道。当我尝试找出(2^127)-1或170141183460469231731687303715884105727 (顺便说一句，它是)105727是质数时，并不令人印象深刻。程序运行了很长时间，我最终不得不停止它。所以，我开始寻找一些更快的语言来写它，所以我用C语言写了程序。它更快，但超大素数的问题开始起作用了。我本想看看是否有解决方案，但后来我从小道消息中听说，如果你用数字编程，Fortr
浏览 0提问于2014-06-28得票数 2
1回答
目前用来计算大数因子的传统算法是什么，以确定它们是否是互换性的，或者如果有一种不计算因子的方法，它会是什么？
我正在为文件和消息创建RSA加密。我需要能够找到同质，但我遇到了一个问题，我试图检查两个大数是否是素数；我使用了我对小数字的方法，我必须尝试找出这个数字的任何因素，如果不能，我会声明它为质数。由于我的数字大小在400到1024位之间，这是行不通的，我修改了我的代码，改为使用原始测试。现在，我试图计算大量的因子，以确定它们是否是同质的，我想知道这样做的标准惯例是什么。会有人碰巧知道吗？
(我在考虑一种方法，在使用简单的可分性规则的情况下，遍历小数字，直到找到$e$和$(p-1)(q-1)
浏览 0提问于2018-01-02得票数 -1
回答已采纳
1回答
我有一个类似下面的代码，我使用它来查找一个范围内的质数(使用Eratosthenes筛子)，并使用OpenMP进行并行处理。在此之前，我有一个预处理阶段，在那里我标记出所有偶数以及3和5的倍数，以便在这一阶段做更少的工作。试验床的共享L3缓存为12MB，物理内存为32 GB。我使用了12个线程。flag阵列为unsigned char。
#pragma omp parallel for
for (i = 0; i < range; i++)
{
for (j = 5; j < range; j+=2)
{
if( flag[i] == 1 &a
浏览 0提问于2011-09-12得票数 1
回答已采纳
9回答
查找合成数
、、
我有一系列随机数。这个范围实际上是由用户决定的，但它将是最多1000个整数。它们被放置在这个位置：
vector<int> n
值的插入方式如下：
srand(1);
for (i = 0; i < n; i++)
v[i] = rand() % n;
我正在创建一个单独的函数来查找所有非质数的值。这是我现在所拥有的，但我知道这是完全错误的，因为我在这个系列中同时得到了质数和复合数。
void sieve(vector<int> v, int n)
{
int i,j;
for(i = 2; i <= n; i++)
{
浏览 0提问于2008-10-29得票数 1
回答已采纳
我正在通过一些项目euler问题来练习我的scala。对于问题7，我必须找到第1000个素数。我有一个有效的解决方案，但没有感觉到它的功能性。 def first_n_primes(n: Long) : List[Long] = {
var last_prime = 1L
(1L to n).map(x => {last_prime = get_next_prime(x, last_prime); last_prime}).toList
} 具体地说，我觉得可能有一种方法可以去掉var last_prime，但我不知道如何使用第n个map评估的结果作为n+1评估
浏览 12提问于2019-03-22得票数 2
回答已采纳
6回答
我在试着解决SPOJ上的一个问题。我们需要计算第n个孪生素数对(素数相差2)。N可以大到10^5。我尝试使用筛子进行预计算，我必须筛选到10^8才能得到最大的n个孪生素数，但时间限制很严格(2s)，而且超时。我注意到人们已经在0.00秒内解决了这个问题，所以我在谷歌上到处寻找公式，但没有找到任何有用的东西。有没有人能给我带路？
提前感谢！！
浏览 2提问于2012-04-13得票数 8
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
