-3

首先，这不是家庭作业……在课外从事这个工作以练习 Java。

public class Problem3 {
public static void main(String[] args) {    
    int n = 13195;

    // For every value 2 -> n
    for (int i=2; i < n; i++) {
        // If i is a multiple of n
        if (n % i == 0) {
            // For every value i -> n
            for (int j=2; j < i; j++) {
                if (n % j != 0) {
                    System.out.println(i); 
                    break;
                }
            }
        }
    }
  }
}

我一直在修改代码，试图让它做我想做的事。

正如问题所说，你应该得到 5、7、13 和 29。

我得到了这些值，再加上 35、65、91、145、203、377、455、1015、1885 和 2639。我认为我走在正确的轨道上，因为我有所有正确的数字......只有几个额外的。

在检查一些既能被 n 整除又是素数的数字时，这里的问题是额外的数字不是素数。不知道发生了什么。

如果有人有任何见解，请分享。

4

5 回答 5

2

这部分

for (int j=2; j < i; j++) {
    if (n % j != 0) {
        System.out.println(i); 
        break;
    }

不检查是否i是素数。除非i很小，否则总会i在某个时候打印出来，因为有比i这小的数字不会除n。所以基本上，这将打印出所有除数（例如，n它不会打印除数，但这是一个例外）。4n == 12

另请注意，算法 - 使用long而不是int避免溢出 - 即使固定检查除数是否i是决定是否打印它的素数，也需要很长时间才能运行实际目标。您应该进行调查以找到更好的算法（提示：您可能想要找到完整的素数分解）。

于 2013-01-15T23:19:56.267 回答
1

我用 Java 解决了这个问题并查看了我的解决方案，明显的建议是开始使用 BigInteger，查看 java.math.BigInteger 的文档

还有很多这些问题是“数学”问题，就像它们是“计算机科学”问题一样，所以更多地研究数学，确保你在提出算法之前合理地理解数学。蛮力有时会奏效，但通常有一些技巧可以解决这些问题。

于 2013-02-02T02:16:34.667 回答
0

你在课外解决这些问题真是太好了。看到你的代码。您正在主函数/线程内编写程序代码。而是先编写函数并从算法上逐步思考。解决这个问题的简单算法可以是这样的：

  • 1) 从最小质数 2 到 13195/2 连续生成数字。（任何数字的因数总是小于其值的一半）
  • 2) 检查生成的数是否为素数。
  • 3）如果数字是素数，则检查它是否是13195的因数；
  • 4) 返回最后一个素数，因为它将是 13195 的最大素数；

另一个建议是尝试编写单独的函数以避免代码复杂性。代码是这样的...

    public class LargestPrimeFactor {

public static long getLargestPrimeFactor(long num){

   long largestprimefactor = 0;

   for(long i = 2; i<=num/2;i++){

       if(isPrime(i)){

           if(num%i==0){


               largestprimefactor = i;

               System.out.println(largestprimefactor);

           }            
       }              
   }

   return largestprimefactor;

}

public static boolean isPrime(long num){

    boolean prime=false;
    int count=0;
    for(long i=1;i<=num/2;i++){

        if(num%i==0){


            count++;

        }
        if(count==1){

            prime = true;

        }
        else{

            prime = false;
        }           
    }

    return prime;

}



public static void main(String[] args) {

    System.out.println("Largest prime factor of 13195 is "+getLargestPrimeFactor(13195));

}

}

于 2014-06-30T08:24:03.333 回答
0

不了解Java，但如果有帮助，这是我的C代码。

# include <stdio.h>
# include <math.h>

// A function to print all prime factors of a given number n
void primeFactors(long long int n)
{
// Print the number of 2s that divide n
while (n%2 == 0)
{
printf("%d ", 2);
n = n/2;
}
int i;
// n must be odd at this point. So we can skip one element (Note i = i +2)
for ( i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, print i and divide n
while (n%i == 0)
{
printf("%d ", i);
n = n/i;
}
}

// This condition is to handle the case whien n is a prime number
// greater than 2
if (n > 2)
printf ("%ld ", n);
}

/* Driver program to test above function */
int main()
{
long long int n = 600851475143;
primeFactors(n);
return 0;
}
于 2013-12-21T06:27:00.140 回答
0

蛮力也可以用来检查这个问题的因素是否是素数……例如。

     for(i=1;i<=n;i++)// n is a factor.
      {
        for(j=i;j>=1;j--)
          {
             if(i%j==0)
              { 
                  counter++;// set counter=0 befor.
              }
             if(counter==2) // for a prime factor the counter will always be exactly two.
             {
                  System.out.println(i);
              }
              counter=0;   
          }
      }
于 2013-01-31T22:11:38.810 回答