We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #3: Largest prime factor
  4. Discussions

Project Euler #3: Largest prime factor

Sort by

recency

|

481 Discussions

|

  • ApolionXD
     + 0 comments

    Java: I dont know how to make it faster...

    public class Solution {
    private static Map<Long,Boolean> primeMap = new HashMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            long n = in.nextLong();
            for(long i=n;i>2;i--){
                if(n%i!=0)
                    continue;
                
                boolean iIsPrime = true;
                if(!primeMap.containsKey(i)){
                    for(int j=2;j<=Math.sqrt(i);j++){
                        if(i%j==0&&j!=i){
                            iIsPrime=false;
                            break;
                        }
                    }
                    primeMap.put(i, iIsPrime);
                } else {
                    iIsPrime = primeMap.get(i);
                }
                
                if(iIsPrime){
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

  • snehilgamit55
     + 0 comments
            long factor = 2;
        while(factor*factor<=n){
            if(n%factor==0){
                n /= factor;
            }else{
                factor++;
            }
        }
        System.out.println(n);
    }

  • kpyadav_bbsr
     + 0 comments

    This was a bit complex. but passed all tests

    def factor(n):
    (res_list, i)=([1],2)
    while n != 1:
        if n%i == 0:
            while n%i == 0:
                n = n//i            
            res_list.append(i)
        i = i+1 if i*i <= n else n
    return res_list

  • yonahel
     + 0 comments

    Haskell

    import Control.Applicative
import Control.Monad
import System.IO

largestPrime :: [Int] -> Int -> Int
largestPrime list max 
    | (length list) == 1 = max
    | otherwise = last list
    
factorize :: Int -> Int -> [Int]
factorize _ 1 = [] 
factorize m n 
    | m * m > n = [n]
    | n `mod` m == 0 = m : factorize m (n `div` m)
    | otherwise = factorize (m + 1) n


main :: IO ()
main = do
    t_temp <- getLine
    let t = read t_temp :: Int
    forM_ [1..t] $ \a0  -> do
        n_temp <- getLine
        let n = read n_temp :: Int
        let factors = factorize 2 n         
        putStrLn(show (largestPrime factors n))

  • charbelmattaLB
     + 0 comments

    can anyone make my code more optimized

    import java.io.; import java.util.;

    public class Solution {

    public static int largestPrimeDivisor(long n) {
    int largestPrime = -1;


    while (n % 2 == 0) {
        largestPrime = 2;
        n /= 2;
    }


    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            largestPrime = i;  
            n /= i;  // Remove the factor i from n
        }
    }


    if (n > 1) {
        largestPrime = (int) n; 
    }

    return largestPrime;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();  

    for (int testCaseIndex = 0; testCaseIndex < t; testCaseIndex++) {
        long n = in.nextLong();  

        int result = largestPrimeDivisor(n);
        System.out.println(result); 
    }

    in.close();
}

    }