Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
3 beğenilme 0 beğenilmeme
1.5k kez görüntülendi
En büyük asal çarpan nasıl bulunur?

$600851475143$ sayısının en büyük asal çarpanı nedir?
Veri Bilimi kategorisinde (470 puan) tarafından  | 1.5k kez görüntülendi

2 Cevaplar

1 beğenilme 0 beğenilmeme

Bu soruyu Eratosthenesin elegini (Sieve of Eratosthenes) kullanarak cozdum.

Bu algoritma bize $n$ e kadar olan asal sayilari verir. Kisaca soyle isler,
 

2 den N e kadar olan sayilari yaz

isaretlenmemis sayi kalmayana kadar:
        isaretlenmemis en kucuk sayiyi bul
        asallara ekle
        katlarini isaretle
        

Eratosthenesin elegi $O(n)$ hafiza ve $O(n\log\log n)$ islem gerektirir. $n$ elemani da isaretleyebilmemiz gerektigi icin $O(n)$ hafiza gerekir. Islem sayisi ise asallarin terslerinin toplaminin ust sinirindan gelmektedir.

Asallari bulduktan sonra en buyuk asaldan en kucuk asala dogru bolme kontrol ederek istenilen sonuc elde edilebilir. Asagida Bunu hesaplayan C kodunu paylastim. Bu kod icin daha onceden su soruda acikladigimiz Liste veri yapisini asallari saklamak icin kullandim.

 

#include <stdlib.h>
#include <stdio.h>
#include "linked_list.h"



long int
sifir_bul (long int limit, char *sayilar, int baslama_indeksi)
{				// baslama indeksinden itibaren bir dizinin icinde ilk sifiri verir isaretlenmis sayiyi bulmak icin fonksiyon

  int ret = -1;
  for (long int ctr = baslama_indeksi; ctr < limit; ctr++)
    {
      if (sayilar[ctr] == 0)
	{
	  ret = ctr;
	  break;
	}
    }
  return ret;
}

void
asallari_bul (Liste * asallar, long int limit)
{
  char *sayilar = calloc (limit, sizeof (char));	// bir tane dizi olustur dizinin n indeksindeki deger bize n-2 nin asal olup olmayacagini soyleyecek
  if (sayilar == NULL)
    {
      printf ("alloke edemedi kapaniyorum");
      exit (0);
    }
  long int indeks = 0;

  while (indeks != -1)
    {				// isaretlenmemis sayi kalmayana kadar yap
      //printf("indeks : %d \n",indeks);

      long int asal = indeks + 2;	//
      basa_eleman_ekle (asallar, asal);	//  sayiyi asallar listesine ekle

      for (long int temp = indeks; temp < limit; temp = temp + asal)
	{
	  sayilar[temp] = 1;	// sayiyinin kaylarini isaretle
	}
      indeks = sifir_bul (limit, sayilar, indeks);	// isaretlenmemis ilk sayiyi bul     
    }
  free (sayilar);		// sayilar dizisine iihtiyacimiz kalmadi yokedebiliriz
}


int
main ()
{
  Liste asallar;

  asallar.ilk_eleman = NULL;
  asallar.son_eleman = NULL;
  asallar.eleman_sayisi = 0;


  long int n = 600851475143;
  long int sqrt_n = 775147;

  asallari_bul (&asallar, sqrt_n);

  Eleman *e = asallar.ilk_eleman;

  while (e != NULL)
    {

      if (n % e->veri == 0)
	{
	  printf ("%ld, %ld yi boler \n", e->veri, n);
	}
      e = e->adres;

    }
}

 

(1.6k puan) tarafından 
tarafından düzenlendi
0 beğenilme 0 beğenilmeme

Ben de Python'da böyle hesaplattım.

x = 600851475143

#verilen n sayisinin asal olup olmadigini kontrol et
def is_prime(n) :
    for i in range(2,int(n**0.5)+1) :
        if n % i == 0 :
            return False
    return True

i=2 #en kucuk asalla basla

while i * i < x+1 : #x'i bolen asallar karekokunden kucuk esit olur 
    if is_prime(i): #i sayisi asalsa devam et
        while x % i == 0 :  #x'i bolen i'nin butun kuvvetlerini yok et
            x = int(x / i) 
            if x == 1 :
                break
            else :
                n = x
    i = i + 1

print(n)

 

(470 puan) tarafından 
tarafından düzenlendi
acaba ne kadar islem yapiyorsunuz ?
yanlış hesaplamadıysam eğer 1471 gibi birşey sanırım
asimptotik $O(\cdot)$ notasyonu anlaminda sormustum. $n$ inci asal sayiyi bulmak icin kac islem gibi.
Yanıt $6857$ olduğuna göre $1471$ işlem yapmış olamazsınız yönteminizle.
20,282 soru
21,821 cevap
73,503 yorum
2,527,032 kullanıcı