7 
#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

プロジェクトオイラーの問題3で指定された番号600851475143の素因数を見つけようとしています （最高の素因数を要求しますが、すべてを見つけたいと思います）。ただし、このプログラムを実行しようとすると、結果が得られません。それは私のプログラムがそのような大きな数にかかる時間と関係がありますか、それとも数自体と関係がありますか？

また、この問題を解決するためのより効率的な方法は何ですか。また、問題を解決しているときに、これらのより洗練されたソリューションに向けてどのように舵を切ることができるかについてのヒントはありますか？

いつものように、ありがとう！

4

12 に答える 12

28

あなたのアルゴリズムは間違っています。あなたは私を必要としません。試行除算による整数因数分解の擬似コードは次のとおりです。

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    if n > 1
        output n

適切な整数データ型を使用してC++に変換するのはあなたに任せます。

編集：比較を修正し（ありがとう、ハロルド）、ボブ・ジョンのディスカッションを追加しました：

これを理解する最も簡単な方法は、例によるものです。n=13195の因数分解を考えてみましょう。最初はz=2ですが、13195を2で割ると余りが1になるため、else句でz = 3に設定され、ループします。ここで、nは3または4で割り切れませんが、z = 5の場合、13195を5で割ったときの余りはゼロなので、5を出力し、13195を5で割ると、n=2639およびz=5は変わりません。ここで、新しいn = 2639は5または6で割り切れませんが、7で割り切れるので、7を出力し、n = 2639/7=377に設定します。ここでz=7を続行すると、除算と同様に余りが残ります。 8、9、10、11、12ですが、377/13 = 29で余りがないため、13を出力し、n=29に設定します。この時点でz=13、z * z = 169、つまり29より大きいため、29は素数であり、13195の最終係数であるため、29を出力します。完全な因数分解は5 * 7 * 13 * 29=13195です。

試行除算を使用して整数を因数分解するためのより優れたアルゴリズムと、試行除算以外の手法を使用する整数を因数分解するためのさらに強力なアルゴリズムがありますが、上記のアルゴリズムで開始でき、Project Euler＃3には十分です。さらに準備ができたら、こちらをご覧ください。

于 2012-08-12T17:38:06.270 に答える
4

@user448810の擬似コードを使用したC++実装：

#include <iostream>
using namespace std;

void factors(long long n) {
    long long z = 2;
    while (z * z <= n) {
        if (n % z == 0) {
            cout << z << endl;
            n /= z;
        } else {
            z++;
        }
    }
    if (n > 1) {
        cout << n << endl;
    }
}

int main(int argc, char *argv[]) {
    long long r = atoll(argv[1]);
    factors(r);
}

// g++ factors.cpp -o factors ; factors 600851475143

同じアルゴリズムを使用したPerlの実装を以下に示します。
実行速度は約10〜15倍遅くなります（n = 600851475143の場合はPerl0.01秒）

#!/usr/bin/perl
use warnings;
use strict;

sub factors {
    my $n = shift;
    my $z = 2;
    while ($z * $z <= $n) {
        if ( $n % $z ) {
            $z++;
        } else {
            print "$z\n";
            $n /= $z;
        }
    }
    if ( $n > 1 ) {
        print "$n\n"
    }
}

factors(shift);

# factors 600851475143
于 2015-10-29T18:15:07.987 に答える
3

600851475143がintの範囲外です

void whosprime(int x) //<-----fix heere ok?
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {... 
      ...
于 2012-08-12T17:31:19.723 に答える
0

編集：私は間違っています（コメントを参照）。私は削除したでしょうが、私が間違っている方法は、プログラムの具体的な内容が出力を生成するのに非常に長い時間がかかることを示すのに役立ちましたので、そのままにしておきます:-)

このプログラムはすぐに印刷されます1（それが素数であるかどうかについては議論しません。それはあなたのプログラムが行うことです）。したがって、何も表示されない場合、問題は実行速度ではなく、プログラムの実行方法に問題があります。

于 2012-08-12T17:43:26.397 に答える
0

以下のコードを試してください：

counter = sqrt(n)
i = 2;

while (i <= counter)
    if (n % i == 0)
        output i
    else
        i++
于 2012-08-12T17:44:00.397 に答える
0

これは、任意の数の最大の素因数を見つけるために非常にうまく機能した私のコードです：

#include <iostream>
using namespace std;

// --> is_prime <--
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // --> nextPrime <--
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

非常に大きな数の最大の素因数を見つけたい場合は、「int」ではなく「long」変数型を使用し、アルゴリズムを微調整して処理を高速化する必要があることに注意してください。

于 2016-06-15T07:42:05.537 に答える
0

短くて明確なバージョン：

    int main()
    {
        int MAX = 13195;

        for (int i = 2; i <= MAX; i++)
        {
             while (MAX % i == 0)
             {
                  MAX /= i;
                  cout <<  i << ", " << flush;   // display only prime factors
             }
        return 0;
    }
于 2016-07-20T20:41:09.090 に答える
0

これは、あなたの質問の最も簡単で理解しやすい解決策の1つです。上記の他のソリューションのように効率的ではないかもしれませんが、私のような初心者の人にとってはそうです。

int main() {

int num = 0;
cout <<"Enter number\n";
cin >> num;
int fac = 2;  
while (num > 1) {
    if (num % fac == 0) {
        cout << fac<<endl;
        num=num / fac;
    }
    else fac++;
}
return 0;

}

于 2017-05-24T09:54:23.900 に答える
0 
# include <stdio.h>
# include <math.h>
void primeFactors(int n)
{
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }
   if (n > 2)
        printf ("%d ", n);
}
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}
于 2017-09-13T11:21:35.667 に答える
0

簡単な方法：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll largeFactor(ll n)
{
        ll ma=0;
        for(ll i=2; i*i<=n; i++)
        {
            while(n%i == 0)
            {
                n=n/i;
                ma=i;
            }
        }
        ma = max(ma, n);
        return ma;
}

int main() 
{
    ll n;
    cin>>n;
    cout<<largeFactor(n)<<endl;
    return 0;
}

プライムシーブイデオンを使用した実装。

于 2018-09-13T08:59:52.960 に答える
0

600851475143はintの範囲外であり、単一のlong型はここでは機能しないため、ここで解決するには、typedefを使用して独自の型を定義する必要があります。現在、llの範囲は約9,223,372,036,854,775,807です。

typedef long long int LL

于 2018-12-06T15:06:48.583 に答える
-2

このコードを試してください。絶対にそれは最高で最も効率的です：

long long number;
bool isRepetitive;

for (int i = 2; i <= number; i++) {
    isRepetitive = false;
    while (number % i == 0) {
        if(!isRepetitive){
            cout << i << endl;
            isRepetitive = true;
        }
        number /= i;
    }
}

楽しみ！☻</p>

于 2015-10-29T16:59:21.983 に答える