数の正確な約数をすべて見つけたい。現在私はこれを持っています：
{
int n;
int i=2;
scanf("%d",&n);
while(i<=n/2)
{
if(n%i==0)
printf("%d,",i);
i++;
}
getch();
}
それを改善する方法はありますか？
55149 次
7 に答える
61
まず、コードの条件はi <= n/2、である必要があります。そうでない場合、要因の1つを見逃す可能性があります。たとえば、n=12の場合は6が出力されません。
数値の平方根（つまりi <= sqrt(n)）までループを実行し、との両方を出力iしn/iます（両方ともnの倍数になります）。
{
int n;
int i=2;
scanf("%d",&n);
while(i <= sqrt(n))
{
if(n%i==0) {
printf("%d,",i);
if (i != (n / i)) {
printf("%d,",n/i);
}
}
i++;
}
getch();
}
ノート ：
- 完全な正方形の場合、平方根が2回出力されない
i*i == nように、@ chepnerによって提案されているように、ループの最後に追加のチェックが実行されます。 - すべての要素を昇順で配列に格納する場合は、ループの最後ですべての数値を並べ替えて表示します。
于 2012-07-28T08:03:13.053 に答える
4
C（高速）で最大18桁の「すべての素因数を検索」を使用して、すべての除数を検索します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) {
unsigned int lastdiv = 0;
divisors[lastdiv++] = 1;
unsigned long long powerfactor = 1;
unsigned long long number = N;
while ((number & 1) == 0) {
powerfactor <<= 1;
divisors[lastdiv++] = powerfactor;
number >>= 1;
}
unsigned long long factor = 3; unsigned long long upto = lastdiv;
powerfactor = 1;
while (factor * factor <= number) {
if (number % factor == 0) {
powerfactor *= factor;
for (unsigned int i = 0; i < upto; i++)
divisors[lastdiv++] = divisors[i] * powerfactor;
number /= factor;
}
else {
factor += 2; upto = lastdiv;
powerfactor = 1;
}
}
if (number > 1) {
if (number != factor) {
upto = lastdiv;
powerfactor = 1;
}
powerfactor *= number;
for (unsigned int i = 0; i < upto; i++)
divisors[lastdiv++] = divisors[i] * powerfactor;
}
return lastdiv;
}
int cmp(const void *a, const void *b) {
if( *(long long*)a-*(long long*)b < 0 ) return -1;
if( *(long long*)a-*(long long*)b > 0 ) return 1;
return 0;
}
int main(int argc, char *argv[]) {
unsigned long long N = 2;
unsigned int Ndigit = 1;
if (argc > 1) {
N = strtoull(argv[1], NULL, 10);
Ndigit = strlen(argv[1]);
}
unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344,
2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680};
unsigned long long divisors[maxdiv[Ndigit]];
unsigned int size = FindDivisors(divisors, N);
printf("Number of divisors = %u\n", size);
qsort(divisors, size, sizeof(unsigned long long), cmp);
for (unsigned int i = 0; i < size; i++)
printf("%llu ", divisors[i]);
printf("\n");
return 0;
}
于 2015-02-15T20:57:54.263 に答える
2
単純な線形探索は、最初に2のすべての因子を捨てることによって改善できます。これは、単純なビットシフト、または優れた組み込み関数を使用してトレーニングゼロをカウントすることによって実行できます。どちらの場合も非常に高速です。次に、shgによって提案されたアルゴリズムを実行し（2の累乗が存在しないため、はるかに高速に実行されます）、結果を2の可能なすべての累乗と組み合わせます（この手順を忘れないでください）。トレーニングゼロがたくさんある入力には大いに役立ちますが、そうでない場合でも役立ちます。除数をテストする必要がなくなるため、ループの長さが半分になります。
一定の低い係数（ただし2より大きい）を捨てることも役立ちます。定数を使用したモジュロは、コンパイラによってほぼ確実に最適化されます（そうでない場合は、自分で実行できます）が、さらに重要なことは、テストする除数が少なくなることを意味します。その要素をあなたが見つけた除数と組み合わせるのを忘れないでください。
数値を完全に因数分解して（お気に入りのアルゴリズムを使用する-おそらくポラードのローが最適です）、因数のすべての製品（空の製品と完全な製品を除く）を印刷することもできます。これは、より大きな入力に対してより速くなる可能性があります-ポラードのRhoアルゴリズムは、単純な線形探索と比較して非常に迅速に因子を検出し、通常、適切な除数よりも因子が少なく、最後のステップ（積を列挙する）は高速な数学のみを含みます（分割なし）。これは主に、Rhoが最も速く見つける非常に小さな因子を持つ数に役立ちます。
于 2012-07-28T08:28:31.693 に答える
1
これは私の新しいC＃バージョンです。Rndmのおかげで、最初の試行よりもほぼ50倍高速です。
public static long GetDivisors(long number)
{
long divisors = 0;
long boundary = (long)Math.Sqrt(number);
for (int i = 1; i <= boundary; i++)
{
if (number % i == 0)
{
divisors++;
if(i != (number / i))
{
if (i * i != number)
{
divisors++;
}
}
}
}
return divisors;
}
于 2016-07-22T10:44:03.997 に答える
0
回答の1つに示されているコードには、一見しただけではわかりにくいバグがあります。sqrt（n）が有効な除数の場合。ただし、nは完全な平方数ではないため、2つの結果は省略されます。
たとえば、試してみてn = 15、何が起こるかを確認します。sqrt(15) = 3、したがって、whileループの最後の値は2です。次に実行if (i * i == n)されるステートメントは、として実行されif(3 * 3 == 15)ます。したがって、3は除数としてリストされておらず、5も欠落しています。
以下は、正の整数の一般的なケースを正しく処理します。
{
int n;
int i=2;
scanf("%d",&n);
while(i <= sqrt(n))
{
if(n%i==0) {
printf("%d,",i);
if (i != (n / i)) {
printf("%d,",n/i);
}
}
i++;
}
getch();
}
于 2015-05-11T09:21:38.177 に答える
0
int count = 2;
//long childsum = 0;
long _originalvalue = sum;
dividend = "1";
for (int i = 2; i < sum; i++)
{
if (_originalvalue % i == 0)
{
sum = _originalvalue / i;
//sum = childsum;
dividend = dividend + "," + i+","+sum;
if (sum == i)
{
count++;
}
else
{
count = count + 2;
}
}
}
return count;
于 2015-07-04T10:52:42.317 に答える
0
与えられた数が奇数の場合、偶数をスキップすることもできます。受け入れられたコードのわずかな即興:)
ここでは、指定された数の因子を見つけるためのJavaコードです。
import java.util.Scanner;
public class Factors {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t=scanner.nextInt();
while(t-- > 0) {
int n = scanner.nextInt();
if(n % 2 == 0) {
for(int i = 1; i <= Math.sqrt(n); i++) {
if(n % i == 0) {
System.out.println(i + ", ");
if(i != n/i) {
System.out.println(n/i + ", ");
}
}
}
}
else {
for(int i = 1; i <= Math.sqrt(n); i=i+2) {
if(n % i == 0) {
System.out.println(i + ", ");
if(i != n/i) {
System.out.println(n/i + ", ");
}
}
}
}
}
}
}
于 2016-02-19T09:13:08.837 に答える