$600851475143$ sayısının en büyük asal çarpanı nedir?

Question

En büyük asal çarpan nasıl bulunur?

$600851475143$ sayısının en büyük asal çarpanı nedir?

Answer 1

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;

    }
}

 

Answer 2

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)

 

Comments

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.