-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代わりに使用するアルゴリズムは、除数が素数であるかどうかをチェックして印刷するかどうかを決定するように修正されたとしても、実際のターゲットに対して実行するのに長い時間がかかることに注意してください。より良いアルゴリズムを見つけるために調査する必要があります (ヒント: 完全な素因数分解を見つけたいと思うかもしれません)。inti

于 2013-01-15T23:19:56.267 に答える
1

私はJavaでこの問題を解決し、私の解決策を見ると、明らかなアドバイスはBigIntegerの使用を開始することです.java.math.BigIntegerのドキュメントを見てください

また、これらの問題の多くは「コンピューター サイエンス」の問題であると同時に「数学」の問題でもあるため、アルゴリズムを考え出す前に、数学をさらに研究し、数学を十分に理解していることを確認してください。ブルート フォースが機能する場合もありますが、多くの場合、これらの問題には裏技があります。

于 2013-02-02T02:16:34.667 に答える
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 に答える
0

あなたがクラスの外でそのような問題に取り組んでいるのはとても良いことです. あなたのコードを見ました。メイン関数/スレッド内に手続き型コードを記述しています。代わりに、関数を記述し、最初にアルゴリズム的に段階的に考えます。この問題を解決する単純なアルゴリズムは次のようになります。

  • 1) 最小の素数である 2 から 13195/2 まで連続して数を生成します。(どの数値も常にその値の半分より小さい因数を持ちます)
  • 2) 生成された数が素数かどうかを確認します。
  • 3) 数が素数の場合、13195 の因数であるかどうかを確認します。
  • 4) 13195 の最大の素因数になるため、最後の素因数を返します。

もう 1 つのアドバイスは、コードの複雑さを避けるために別の関数を書いてみることです。コードはこんな感じ…

    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 に答える