3

合成数を入力として受け入れています。そのすべての因数と、その数の最大の素因数を印刷したいと思います。私は次のコードを書きました。51という数字までは問題なく動作しています。ただし、51より大きい数字を入力すると、間違った出力が表示されます。コードを修正するにはどうすればよいですか？

#include<stdio.h>
void main()
{
 int i, j, b=2, c;
 printf("\nEnter a composite number: ");
 scanf("%d", &c);
 printf("Factors: ");

 for(i=1; i<=c/2; i++)
 {
  if(c%i==0)
  {
   printf("%d ", i);
   for(j=1; j<=i; j++)
   {
    if(i%j > 0)
    {
     b = i;
    }
    if(b%3==0)
     b = 3;
    else if(b%2==0)
     b = 2;
    else if(b%5==0)
     b = 5;
   }
  }
 }
 printf("%d\nLargest prime factor: %d\n", c, b);
}
4

5 に答える 5

8

これは少しスポイラーなので、これを自分で解決したい場合は、まだ読んではいけません:)。ヒントを順番に提供していきますので、各ヒントを順番に読むことができます。さらにヒントが必要な場合は、次のヒントに移動してください。

ヒント＃1： 除数がnの約数である場合、n/除数もnの約数です。たとえば、100/2 = 50で、余りは0なので、2は100の約数です。ただし、これは、50が100の約数であることも意味します。

ヒント＃2 ヒント＃1が与えられた場合、これは、素因数をチェックするときにi=2からi*i<=nにループできることを意味します。たとえば、数値100をチェックしている場合、ヒント＃1を使用するとすべての要素が得られるため、10にループするだけで済みます（10 *10は<=100）。あれは：

100 / 2 = 50, so 2 and 50 are factors
100 / 5 = 20, so 5 and 20 are factors
100 / 10 = 10, so 10 is a factor

ヒント＃3 nの素因数だけを気にするので、nの最初の因数を見つけて除数と呼ぶだけで十分です。そうすれば、n/除数の他の因数を再帰的に見つけることができます。ふるいアプローチを使用して、要素を見つけたらマークを付けることができます。

ヒント＃4 サンプルソリューションC：

bool factors[100000];

void getprimefactors(int n) {
  // 0 and 1 are not prime
  if (n == 0 || n == 1) return;

  // find smallest number >= 2 that is a divisor of n (it will be a prime number)
  int divisor = 0;
  for(int i = 2; i*i <= n; ++i) {
    if (n % i == 0) {
      divisor = i;
      break;
    }
  }
  if (divisor == 0) {
    // we didn't find a divisor, so n is prime
    factors[n] = true;
    return;
  }

  // we found a divisor
  factors[divisor] = true;
  getprimefactors(n / divisor);
}

int main() {
  memset(factors,false,sizeof factors);
  int f = 1234;
  getprimefactors(f);
  int largest;
  printf("prime factors for %d:\n",f);
  for(int i = 2; i <= f/2; ++i) {
    if (factors[i]) {
      printf("%d\n",i);
      largest = i;
    }
  }
  printf("largest prime factor is %d\n",largest);
  return 0;
}

出力：

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
prime factors for 1234:
2
617
largest prime factor is 617
> Terminated with exit code 0.
于 2010-08-12T18:58:47.137 に答える
3

学ぶためにやっていると思いますので、ヒントをいただければ幸いです。

まず、失敗した数値でアルゴリズムをステップ実行します。これはエラーの場所を示していますか?

于 2010-08-12T18:31:56.730 に答える
2

素数 2、3、および 5 を計算するだけでなく、コードが特定の数のすべての素数を見つけるように再コーディングする必要があります。素数または 2、3、または 5 の倍数です。ただし、7、11、13、17、19 も素数です。したがって、コードは、特定の数のすべての因数を見つけることによって単純に機能し、最大の因数を返す必要があります。はさらに割り切れません。

于 2010-08-12T18:31:17.533 に答える
0

実際、これは最小の数（たとえば、100,000未満）を除いて非常に遅いです。数の素因数だけを見つけてみてください。

#include <cmath>

void addfactor(int n) {
    printf ("%d\n", n);
}

int main()
{
    int d;
    int s;
    int c = 1234567;
    while (!(c&1)) {
        addfactor(2);
        c >>= 1;
    }
    while (c%3 == 0) {
        addfactor(3);
        c /= 3;
    }
    s = (int)sqrt(c + 0.5);
    for (d = 5; d <= s;) {
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 2;
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 4;
    }
    if (c > 1)
        addfactor(c);
    return 0;
}

ここで、addfactorは、素因数のリストに因子を追加するある種のマクロです。これらを入手したら、数のすべての要素のリストを作成できます。

これは、ここに投稿された他のコードスニペットよりも劇的に高速です。10597959011のようなランダム入力の場合、私のコードは除数を再構成するために2000ビット演算と1000以上の演算を必要としますが、他のコードは数十億の演算を必要とします。その場合、「インスタント」と「分」の違いです。

于 2010-08-12T18:59:13.717 に答える
0

dcpの答えの単純化（反復的な方法で）：

#include <stdio.h>
void factorize_and_print(unsigned long number) {
  unsigned long factor;
  for(factor = 2; number > 1; factor++) {
    while(number % factor == 0) {
      number = number / factor;
      printf("%lu\n",factor);
    }
  }
}

/* example main */
int main(int argc,char** argv) {
  if(argc >= 2) {
    long number = atol(argv[1]);
    factorize_and_print(number);
  } else {
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]);
  }
}

注: ここには、argv の数値を正しく取得していない数値解析バグがあります。

于 2012-10-21T03:20:18.467 に答える