我正在尝试在python中实现eratosthenes的筛子,但是当试图找到所有素数达到sqare根时,例如779695003923747564589111193840021我得到一个错误,说range()的结果有太多的项目.我的问题是,我如何避免这个问题,如果我用while循环实例化列表,我会得到一个错误,说我使用了太多的内存(在它开始使用页面文件之前),下面列出了两个:
使用范围()
maxnum = 39312312323123123
primes = []
seq = []
i = 0
seq = range(2,maxnum)
for i in seq:
mul = i * seq
for j in mul:
try:
seq.remove(j)
except:
pass
primes.append(i)
print primes
使用while:
maxnum = 39312312323123123
primes = []
seq = []
i = 0
while i < maxnum:
seq.append(i)
i+=1
for i in seq:
mul = i * seq
for j in mul:
try:
seq.remove(j)
except:
pass
primes.append(i) …Project Euler上的问题#3是:
13195的主要因素是5,7,13和29.
600851475143的最大主要因素是什么？
我的解决方案永远.我认为我得到了正确的实施; 但是,当用大数字进行测试时,我无法看到结果.它永远运行.我想知道我的算法是否有问题:
public class LargestPrimeFactor3 {
public static void main(String[] args) {
long start, end, totalTime;
long num = 600851475143L;
long pFactor = 0;
start = System.currentTimeMillis();
for(int i = 2; i < num; i++) {
if(isPrime(i)) {
if(num % i == 0) {
pFactor = i;
}
}
}
end = System.currentTimeMillis();
totalTime = end - start;
System.out.println(pFactor + " Time: "+totalTime);
}
static boolean isPrime(long n) {
for(int i = 2; i < n; …13195的主要因素是5,7,13和29. 600851475143中最大的素数是多少？
我以自己的方式在Project Euler上解决了这个问题,这很慢,然后我在某人的github帐户上找到了这个解决方案.我无法弄清楚它为何起作用.为什么删除了许多因素,等于索引？任何见解？
def Euler3(n=600851475143):
for i in range(2,100000):
while n % i == 0:
n //= i
if n == 1 or n == i:
return i
我写了一个整数分解函数,但是在弄乱它之后,我意识到它有几个数字的问题......
>>> pFactors(99) # it does work for numbers with multiple of one prime factor
[3, 3, 11]
>>> pFactors(999) # however, sometimes, it doesn't
[3, 37] # the actual prime factorization of 999 is [3, 3, 3, 37].
>>> pFactors(88)
[2, 11]
>>> pFactors(888)
[2, 3, 37]
我的代码有什么问题？
def pFactors(n):
"""Finds the prime factors of 'n'"""
from primes import isPrime
from math import sqrt
pFact, limit, check, num = [], int(round(sqrt(n), 2)) + 1, 2, n
if isPrime(n):
return …我正在解决这个问题:
通过列出前六个素数:
2,3,5,7,11 和13,我们可以看到第6个素数是13. 什么是10个第001个素数？
def checkPrime(x):
facs = 0
for i in range(1,x):
if x%i==0:
facs = facs + 1
if facs == 2:
return True
else :
return False
i = 1
noPrime = 0
done = False
while(done==False):
i = i + 1
print "i = {0} and noPrime={1}".format(i,noPrime)
if checkPrime(i)==True:
noPrime = noPrime + 1
if noPrime==10001 :
print i
done=True
但这需要花费很多时间.
我怎样才能加快速度？
我发现了一些基于Fermat的小定理声称检查素性的Python代码:
def CheckIfProbablyPrime(x):
return (2 << x - 2) % x == 1
我的问题:
我是编程的新手,我的一个朋友建议我应该对Euler项目进行练习以使其更好.我在问题3上遇到了问题:
"13195的主要因素是5,7,13和29. 600851475143中最大的主要因素是什么？"
现在这是我的解决方案:
class Program
{
static void Main(string[] args)
{
long number = 600851475143;
bool prime = true;
for (long i = 3; i <= number; i++)
{
for (long n = 2; n < i; n++)
{
if (i % n == 0)
{
prime = false;
break;
}
}
if (prime)
{
if (number % i == 0)
{
Console.WriteLine(i);
}
}
prime = true;
}
Console.ReadKey();
}
}
现在,虽然我确实得到了正确的答案(这是6857),但我发现我的方法非常低效.如果您将运行我的代码,您将看到它仍将在超过2分钟之后运行...我的问题是如何为此编写更高效/更快的代码？
我正在尝试扩展我对Hackerrank 练习题的解决方案.
总之,问题是找到范围内的素数因子的最大数量.
因为1..500它是4 for 210 -> 2(1), 3(1), 5(1), 7(1)
因为1..5000它是5 for 2310 -> 2(1), 3(1), 5(1), 7(1), 11(1)
为了1..50000它6 for 30030 -> 2(1), 3(1), 5(1), 7(1), 11(1), 13(1)
这是我的解决方案
require 'prime'
max = 0
for d in 1..n
pfs = d.prime_division.count
max = pfs if pfs > max
end
puts max
这需要永远n = 10000000000.
我可能从错误的角度看待解决方案.
如何扩展此解决方案？
我已经开始解决 Rust 中的 Project Euler 问题，并遇到了#3，其中最简单的快速方法是实现埃拉托色尼筛法。
在此过程中，我的算法创建了一个迭代器，然后过滤掉非素数并将其分配回原始向量，但我收到了Vec<u32>无法从 构建的错误Iterator<Item=&u32>。
代码：
fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
let mut primes: Vec<u32> = Vec::new();
let mut range: Vec<u32> = (2..=limit).collect();
let mut length = range.len();
loop {
let p = range[0];
primes.push(p);
range = range.iter().filter(|&n| *n % p != 0).collect();
if length == range.len() {
break;
}
length = range.len();
}
primes
}
错误：
fn eratosthenes_sieve(limit: u32) -> Vec<u32> {
let mut primes: Vec<u32> = …我正在尝试在 Scala 中编写一个递归函数，它接受一个正整数并打印出它的质因数。例如200 = 2, 2, 2, 5, 5。这是我写的代码。
println(calculatePrimeFactors(200,2))
def isPrime( x:Int ):Boolean = {
def recIsP( n:Int, i:Int ) : Boolean = (i == n) || (n % i != 0) && recIsP(n, i + 1)
recIsP(x,2)
}
def calculatePrimeFactors(n:Int,i:Int):String= {
if (i==n) {
""
}else if(isPrime(i) && n%i==0){
i.toString + ", " + calculatePrimeFactors(n,i+1)
}else{
calculatePrimeFactors(n,i+1)
}
}
我的代码输出 2,5, .
我如何才能使代码正常工作并输出2,2,2,5,5,.我尝试使用带有此语句的循环n = n / i，但 Scala 返回一个错误，指出无法重新分配给 val。