1

我的输入是一个Integer. 在该值之前，应该找到所有质数并将其打印在 5 列中，然后我必须对整数进行“质数分解”并打印结果。

挺好用的，就是太慢了。。。

public class Bsp07 {
  public static void main(String[] args) {

     System.out.println("Enter the upper bound for prime number search");
     int n = SavitchIn.readLineInt();
     int[] aZahlen = new int[n - 1];
     for (int el = 0, zahl = 2; el != n - 1; el++, zahl++)
        aZahlen[el] = zahl;

     int p = 2, altesP; // next unmarked number
     boolean aus = false; // when unmarked elements are "aus" (off)

     while (aus == false) {

     // marks Elements; using For loop since for-each loop doesn't work
        for (int i = 0; i < aZahlen.length; i++) {
           if ((aZahlen[i] % p == 0) && (aZahlen[i] != p))
              aZahlen[i] = 0;
        }

        altesP = p; // merkt sich altes p
     // update p, find next unmarked Element
        for (int el : aZahlen) {
           if ((el != 0) && (el > altesP)) {
              p = el;
              break;
           }
        }
     // if p stayed the same unmarked elements are "aus" (off)
        if (altesP == p)
           aus = true;
     }

     int nervVar = 0;
     for (int pr : aZahlen) {
        if(pr==0) 
           continue;
        System.out.print(pr + " ");
        nervVar++;
        if ((nervVar % 5 == 0)) System.out.print("\n");
     }

     /* Factorization */
     System.out.print("\n" + n + " = ");
     for (int i = 0, f = 0; n != 1; i++, f++) {
        while(aZahlen[i]==0) i++;
     /*
      * If the prime divides: divide by it, print the prime,
      * Counter for further continuous decrease with prime number if n = 1,
      * Stop
      */
        if (n % aZahlen[i] == 0) {
           n /= aZahlen[i];
        // So that the first time is not *
           if (f != 0)
              System.out.print(" * " + aZahlen[i]);
           else
              System.out.print(aZahlen[i]);
           i--;
        }
        // So that f remains zero if no division by 2
        else
           f--;
     }
     System.out.println();
  }

}

我在哪里可以节省一些资源？顺便说一句，我现在只能使用数组......对不起德国人的评论。只是如果一些真正不必要的长循环或类似的东西引起了你的注意

谢谢！

4

3 回答 3

1

而不是搜索到n-1，我只会搜索到(int) sqrt(n)。自己弄清楚为什么这就足够了。;-)

我不明白你为什么需要altesP。你不能只增加p两个吗？

我不会通过删除来过滤。我会建立一个肯定的列表，并添加你找到的素数。

研究可以排除一个数字而不必经过整个筛子的快速素数测试。

因此，请对您的代码进行以下更改：

  1. 而不是擦除aZahlen，建立一个列表primes。sqrtN = (int)sqrt(n)因为分配大小应该没问题，并使用foundPrimes你知道多少素数的计数。

  2. 迭代p直到<= sqrtN没有任何模糊。看看是否有任何已知的素数是除数，否则你找到了一个新的素数。输出它，并将其存储在您的foundPrimes列表中。

于 2012-12-01T13:30:10.423 回答
-1

Anint[]每个值使用 32 位。如果您使用byte[]它，每个值将使用 8 位，如果您使用 BitSet，它将使用每个值 1 位（小 32 倍）

于 2012-12-01T13:38:07.073 回答
-1

我不确定你想做什么。我认为您正在尝试通过素数的试除法来分解整数。为此，您不需要所有小于整数的素数，只需要小于整数平方根的素数，因此您只需要一个简单的 Eratosthenes 筛来选择素数：

function sieve(n)
  bits := makeArray(2..n, True)
  ps := []
  for p from 2 to n
    if bits[p]
      ps.append(p)
      for i from p+p to n step p
        bits[i] = False
  return ps

然后你可以使用这些素数来执行分解：

function factors(n)
  ps := primes(sqrt(n))
  fs := []
  p := head(ps)
  while p*p <= n
    if n%p == 0
      fs.append(p)
      n := n / p
    else
      ps := tail(ps)
      p := head(ps)
  fs.append(n)
  return fs

我在博客上的一篇文章中讨论了使用素数进行编程，其中包括这两种算法在 Java 中的实现。这篇文章还包括其他更有效的枚举素数和因式分解上面给出的方法。

于 2012-12-01T17:55:04.107 回答