Project Euler # 3 в Java занимает вечность

Хотя не на Java, я думаю, вы, вероятно, сможете разобрать следующее. По сути, необходимо сократить количество итераций, проверяя только нечетные делители и извлечение квадратного корня из числа. Вот метод грубой силы, который дает мгновенный результат на C #.

static bool OddIsPrime (long oddvalue)  // test an odd >= 3 
{
    // Only test odd divisors.
    for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

static void Main(string[] args)
{
    long max = 600851475143;   // an odd value
    long maxFactor = 0;

    // Only test odd divisors of MAX. Limit search to Square Root of MAX.
    for (long i = 3; i <= Math.Sqrt(max); i += 2)
    {
        if (max % i == 0)
        {
            if (OddIsPrime(i))  // i is odd
            {
                maxFactor = i;
            }
        }
    }
    Console.WriteLine(maxFactor.ToString());
    Console.ReadLine();
}

Вы должны разделить на каждый фактор по мере его обнаружения. Тогда нет необходимости проверять их на простоту, когда мы перечисляем возможные делители в порядке возрастания (любой найденный таким образом делитель не может быть составным, его множители уже будут разделены). Тогда ваш код станет:

class LargestPrimeFactor4 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;   // odd value is not divided by any even
        long pFactor = 1L;

        start = System.currentTimeMillis();

        for(long i = 3L; i <= num / i; ) 
        {
            if( num % i == 0 ) {
                pFactor = i;
                num = num / i;
            }
            else {
                i += 2;
            }
        }
        if( pFactor < num ) { pFactor = num; }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println( pFactor + " Time: " + totalTime);
    }
}

public HashSet<Integer> distinctPrimeFactors(int n) //insane fast prime factor generator
{
    HashSet<Integer> factors = new HashSet<Integer>();
    int lastres = n;
    if (n==1)
    {
        factors.add(1);
        return factors;
    }
    while (true)
    {
        if (lastres==1)
            break;
        int c = 2;
        while (true)
        {
            if (lastres%c==0)
                break;
            c++;
        }
        factors.add(c);
        lastres/=c;
    }
    return factors;
}

Если вы хотите быстро сгенерировать различные простые множители для числа, используйте этот метод, который уменьшает число на каждой итерации. Вы можете изменить int на long, и это должно сработать для вас.

Вот псевдокод для целочисленной факторизации пробным делением:

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    output n

Проще всего понять это на примере. Рассмотрим факторизацию n = 13195. Первоначально z = 2, но при делении 13195 на 2 остаток остается 1, поэтому предложение else устанавливает z = 3, и мы выполняем цикл. Теперь n не делится на 3 или на 4, но когда z = 5, остаток при делении 13195 на 5 равен нулю, поэтому выведите 5 и разделите 13195 на 5, так что n = 2639 и z = 5 не изменится. Теперь новое n = 2639 не делится на 5 или 6, но делится на 7, поэтому выведите 7 и установите n = 2639/7 = 377. Теперь мы продолжаем с z = 7, и это оставляет остаток, как и деление. на 8, 9, 10, 11 и 12, но 377/13 = 29 без остатка, поэтому выведите 13 и установите n = 29. В этой точке z = 13 и z * z = 169, что больше 29, поэтому 29 является простым и является последним множителем 13195, поэтому выведите 29. Полная факторизация составляет 5 * 7 * 13 * 29 = 13195.

Существуют лучшие алгоритмы факторизации целых чисел с использованием пробного деления и даже более мощные алгоритмы факторизации целых чисел, которые используют методы, отличные от пробного деления, но алгоритм, показанный выше, поможет вам начать работу, и его достаточно для Project Euler # 3. Когда будете готовы к большему, загляните сюда.

Две вещи для повышения производительности:

static boolean isPrime(long n)
{
    for(int i = 2; i <= sqrt(n); i++)  // if n = a * b, then either a or b must be <= sqrt(n).
    {
        if(n % i == 0)
        {
            return false;
        }
    }        
    return true;
}  

теперь для основного цикла

for(int i = num; i > 1; i--) // your interested in the biggest, so search from high to low until you have a match
{
    if(num % i == 0 && isPrime(i)) // check for num % i == 0 is faster, so do this first
    {
        pFactor = i;
        break; // break if you have a factor, since you've searched from the top
    }
}

Здесь еще есть кое-что, что можно улучшить, но это вам предстоит выяснить. Подумайте об изменении num. Удачи с проектом Эйлер :)

Вы можете просто разложить число на множители, и тогда ответом будет самый большой простой множитель:

import java.util.ArrayList;
import java.util.Collections;

public class PrimeFactorization {

    /* returns true if parameter n is a prime number, 
         false if composite or neither */
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        else if (n == 2) return true;
        for (int i = 2; i < Math.pow(n, 0.5) + 1; i++)
            if (n % i == 0)
                return false;
        return true;
    }

    /* returns smallest factor of parameter n */
    public static long findSmallestFactor(long n) {
        int factor = 2; // start at lowest possible factor
        while (n % factor != 0) { // go until factor is a factor
            factor++; // test the next factor
        }
        return factor;
    }

    /* reduces the parameter n into a product of only prime numbers
       and returns a list of those prime number factors */
    public static ArrayList<Long> primeFactorization(long n) {

        ArrayList<Long> primes = new ArrayList<Long>();
          // list of prime factors in the prime factorization
        long largestFactor = n / findSmallestFactor(n);    

        long i = 2;
        while (i <= largestFactor) { 
          // for all possible prime factors 
          // (2 - largest factor of the number being reduced)

            if (isPrime(i) && n % i == 0) { 
                // if this value is prime and the number is divisible by it

                primes.add(i); // add that prime factor to the list
                n /= i; // divide out that prime factor from the number 
                        // to start reducing the new number
                largestFactor /= i; // divide out that prime factor 
                       // from the largest factor to get the largest 
                       // factor of the new number
                i = 2; // reset the prime factor test
            } else {
                i++; // increment the factor test
            }
        }

        primes.add(n); // add the last prime number that could not be factored
        Collections.sort(primes);
        return primes;
    }
}

А потом назовите это так:

ArrayList<Long> primes = PrimeFactorization.primeFactorization(600851475143L);
System.out.println(primes.get(primes.size() - 1));

Все это занимает всего несколько миллисекунд.

Это не идеальное решение, но оно подойдет для 600851475143.

public static void main(String[] args) {
    long number= 600851475143L;
    int rootOfNumber = (int)Math.sqrt(number)+10;
    for(int i = rootOfNumber; i > 2; i--) {
        if(number % i == 0) {
            if(psudoprime(i)) {
                System.out.println(i);
                break;
            }
        }
    }

}

public static boolean psudoprime(int num) {
    for(int i = 2; i < 100; i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}

public class LargestPrimeFactor {
    static boolean isPrime(long n){
        for(long i=2;i<=n/2;i++){
            if(n%i==0){
                return false;                                               
            }
        }
        return true;    
    }

    static long LargestPrimeFact(long n){
        long largestPrime=0;
        for(long i=2;i<Math.sqrt(n)/2;i++){
            if(n%i==0){
                if(isPrime(i)){
                    largestPrime=i;
                }
                }                                       
            }
        return largestPrime;
    }
    public static void main(String args[]) {
        System.out.println (LargestPrimeFact(600851475143L));
    }
}

Источник: http://crispylogs.com/project-euler-problem-3-solution/

Этот отлично работает !!

public class Puzzle3 {
public static void main(String ar[])
{
    Long i=new Long("1");
    Long p=new Long("600851475143");
    Long f=new Long("1");
    while(p>=i)
    {
        if(p%i==0)
        {
            f=i;
            p=p/i;
            int x=1;
            i=(long)x;
        }
        i=i+2;
    }
    System.out.println(f);
}

}