Największy dzielnik, który jest liczbą pierwszą - program nie działa dla dużej liczby

Czy mógłby mi ktoś powiedzieć czemu ten program działa poprawnie dla liczby 13195 i innych bez problemu, a dla większych jak 600851475143 nic się nie wyświetla? :(

#include <iostream>

using namespace std;

bool isPrime(int number){

    if(number < 2) return false;
    if(number == 2) return true;
    if(number % 2 == 0) return false;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return false;
    }
    return true;
}

int main()
{
    unsigned long long int n=600851475143;
        for(unsigned long long int i=n; i>=1; --i){
        if(n%i==0){
            if(isPrime(i))cout<<i<<" ";
        }
    }

    return 0;
}
 

Twoja funkcja przyjmuje int, więc jak tam przekażesz long long int to się licznik przekręca. Poza tym pewnie się będzie długo liczyło dla dużej liczby.

szweszwe napisał(a):

Twoja funkcja przyjmuje int, więc jak tam przekażesz long long int to się licznik przekręca. Poza tym pewnie się będzie długo liczyło dla dużej liczby.

już każdy int zamieniłam na long long, ale dalej to samo, nawet po 15 minutach sie nie naliczył, może być jakikolwiek inny powód?

A możesz powiedzieć po co Ci ten if?

if(n%i==0){
   if(isPrime(i))cout<<i<<" ";
}

szweszwe napisał(a):

A możesz powiedzieć po co Ci ten if?

if(n%i==0){
   if(isPrime(i))cout<<i<<" ";
}

Jeśli liczba jest podzielna przez 'i' to sprawdzam dalej czy 'i' jest liczbą pierwszą. Jeśli tak to wyświetlam 'i'.

A jakie są zakresy danych wejściowych? Bo na podanym przykładzie to dużo szybciej byłoby przelecieć sitem zakres sqrt(n) a potem przelecieć po liczbach pierwszych w zakresie (z tablicy z sita) i znaleźć największą która dzieli n. To wszystko przy założeniu że da się zmieścić w pamieci tablicę na sito.

Mój naiwny kod w pythonie od razu (w sensie momentalnie) daje odpowiedź że faktoryzacja tej liczby to [71, 839, 1471, 6857]

Więc zrobiłem coś takiego (kody z naszego https://github.com/p4-team/crypto-commons ;) ):

def get_primes(limit=1000000):
    """
    Use sieve to get list of prime numbers in range
    :param limit: range for search
    :return: list of primes in range
    """
    import math
    m = limit + 1
    numbers = [True for _ in range(m)]
    for i in range(2, int(math.sqrt(limit))):
        if numbers[i]:
            for j in range(i * i, m, i):
                numbers[j] = False
    primes = []
    for i in range(2, m):
        if numbers[i]:
            primes.append(i)
    return primes

def factor(n, limit=1000000):
    """
    Factor given value using sieve up to a certain limit
    :param n: number to factor
    :param limit: sieve limit
    :return: list of factors and residue
    """
    factors = []
    primes = get_primes(limit)
    for prime in primes:
        while n % prime == 0 and n > 1:
            n /= prime
            factors.append(prime)
        if n < 2:
            break
    return factors, n

I na podstawie tych 2 funkcji możemy sobie policzyć:

    n = 600851475143
    factors = factor(n, int(math.sqrt(n)))
    print(factors)

Co daje ([71, 839, 1471, 6857], 1L)

luthien napisał(a):

szweszwe napisał(a):

A możesz powiedzieć po co Ci ten if?

if(n%i==0){
   if(isPrime(i))cout<<i<<" ";
}

Jeśli liczba jest podzielna przez 'i' to sprawdzam dalej czy 'i' jest liczbą pierwszą. Jeśli tak to wyświetlam 'i'.

No tak. Jakoś z początku nie pokapowałem się o co chodzi. Kod działa, możesz sprawdzić przez dodanie jakiegoś wypisywania w trakcie ale trwa bardzo długo. Zrób tak jak zasugerował @Shalom i zamiast od n to iteruj od sqrt(n), po wprowadzeniu tych zmian wynik masz natychmiast.

@Shalom @szweszwe Dziękuję!