web-gelistirme-sc.com

Verilen bir tamsayıdaki tüm kesin bölenleri bulmak için algoritma

Bir numaranın tam bölenlerini bulmak istiyorum . Şu anda bu var:

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i<=n/2)
    {
        if(n%i==0)
                  printf("%d,",i);
        i++;
     }
   getch();
}

Bunu geliştirmek için herhangi bir yolu var mı?

19
jairaj

Öncelikle, kodunuz i <= n/2 koşuluna sahip olmalıdır, aksi takdirde faktörlerden birini kaçırabilir, örneğin n = 12 ise 6 basılmaz.

Döngüyü sayının kareköküne getirin (örn. i <= sqrt(n)) ve hem i hem de n/i (her ikisi de n'nin katları olacaktır) yazdırı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();
}

Not : 

  • Mükemmel bir kare için, karekök iki kez yazdırılmayacak şekilde ek kontrol @chepner tarafından önerilen şekilde i*i == n için döngü sonunda yapılır.
  • Artan sırada tüm faktörlerin değerlerini bir dizide saklamak istiyorsanız, o zaman döngünün sonunda tüm sayıları ve ekranı sıralayın. 
54
Rndm

Tüm bölencileri C (hızlı) Ve 18 basamağa kadar "tüm ana faktörleri bulma" kullanarak bulma.

#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;
}
4
ManAndPC

Basit doğrusal arama ilk önce tüm 2 faktörü atmak suretiyle geliştirilebilir. Bu, basit bit kaydırma ile yapılabilir veya Nice intrinsik bir fonksiyonla sıfır antremanı saymak mümkündür. Her iki durumda da çok hızlı. Ardından, shg tarafından önerilen algoritmayı çalıştırın (ki bu, ikisinin güçleri mevcut olmadığından çok daha hızlı çalışacaktır) ve sonucu, ikisinin tüm olası güçleriyle birleştirin (bu adımı unutmayın). Çok fazla eğitim sıfırına sahip olan girdiler için çok yardımcı olur, ancak eğer yapmazlarsa bile yardımcı olur - artık bölenleri bile test etmek zorunda kalmazsınız, böylece döngü yarı yarıya kısalır.

Bazı sabit düşük faktörleri atmak (ancak 2'den büyük) de yardımcı olabilir. Sabit olan bir Modulo derleyici tarafından neredeyse kesinlikle optimize edilmiştir (ya da yoksa kendiniz yapabilirsiniz), ama daha da önemlisi, test etmek için daha az bölen kaldığı anlamına gelir. Bu faktörü bulduğunuz bölenlerle birleştirmeyi unutmayın.

Ayrıca, sayısı tamamen çarpanlara ayırabilirsiniz (en sevdiğiniz algoritmayı kullanın - muhtemelen Pollard's Rho en iyisidir) ve ardından faktörlerin tüm ürünlerini (boş ürün ve tüm ürün hariç) yazdırabilirsiniz. Bunun daha büyük girdiler için daha hızlı olma şansı çok yüksektir - Pollard'ın Rho algoritması basit bir doğrusal aramaya kıyasla çok hızlı bir şekilde faktörler bulur, genellikle uygun bölenlerden daha az faktör vardır ve son adım (ürünlerin numaralandırılması) yalnızca hızlı matematik gerektirir (bölünme yok). Bu çoğunlukla Rho'nun en hızlı bulduğu çok küçük faktörlere sahip sayılar için yardımcı olur.

2
harold

Bu benim yeni C # Sürüm. Rndm sayesinde ilk denememden neredeyse 50 kat daha hızlı.

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;
    }
0
AustrianHunter
  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;
0
Himanshu Jain

Verilen numara tek olduğunda bile sayıları bile atlayabiliriz. Kabul edilen yasada ufak bir doğaçlama :)

Burada verilen sayının faktörlerini bulmak için Java kodu.

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 + ", ");
                        }
                    }
                }
            }
        }
    }
}
0
manohar e

Cevaplardan birinde sunulan kodun ilk bakışta görülmesi zor bir hata var. Eğer sqrt (n) geçerli bir bölen ise; fakat n mükemmel bir kare sayısı değildir, daha sonra iki sonuç alınmaz.

Örneğin. n = 15 dosyasını deneyin ve ne olduğunu görün; sqrt(15) = 3, while süresinin son değeri 2'dir. Bir sonraki deyim if (i * i == n), if(3 * 3 == 15) olarak yürütülür. Yani 3 bölen olarak listelenmemiş, aynı zamanda 5 özledim.

Aşağıdaki, genel olarak pozitif tamsayıları doğru şekilde ele alacaktır.

 {
   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();
}
0
Duckman