我正在开发一个程序,该程序从用户那里获取输入以获得上限,然后使用一种方法来计算从 1 到 N 的所有素数。我有一个可行的解决方案,但我的头脑一直困扰着我,它的效率非常低。
public ArrayList<Integer> primeNumbers()
{
long startTime = System.nanoTime();
ArrayList<Integer> prime = new ArrayList<Integer>();
ArrayList<Integer> factorList;
for (int i = 2; i <= this.limit; i+=1)
{
factorList = factors(i);
if (factorList.size() == 2 && factorList.contains(1) && factorList.contains(i))
{
prime.add(i);
}
}
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("The total time was: " + totalTime);
return prime;
}
public ArrayList<Integer> factors(int i)
{
ArrayList<Integer> factor = new ArrayList<Integer>();
for (int a = 1; a <= i; a+=1)
{
for (int b = 1; b<=i; b+=1)
{
if (a*b == i)
{
if (factor.contains(a) == false)
factor.add(a);
if (factor.contains(b) == false)
factor.add(b);
}
}
}
return factor;
}
尽管上面的代码有效,但似乎进展非常缓慢
this.limit
值高于 3500。关于如何提高效率的任何想法,还是我只是偏执狂?感谢帮助。
您的实现效率非常低,因为它在整数参数的大小上是二次的。
寻找例如 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 来提高复杂性。
我会研究是否有一种不同的方法来分解一个数字,通过您的实现,您将 3 个 for 循环嵌套在彼此内部。 如何分解一个数字 Java 可能会有所帮助
下面是 Java 中 Eratosthenes 筛子的实现:
public static LinkedList sieve(int n)
{
BitSet b = new BitSet(n);
LinkedList ps = new LinkedList();
b.set(0,n);
for (int p=2; p<n; p++)
{
if (b.get(p))
{
ps.add(p);
for (int i=p+p; i<n; i+=p)
{
b.clear(i);
}
}
}
return ps;
}
我在我的博客上讨论了这个功能。