[Python]

def Largest_prime(n):
    cnt = 2
    while cnt < n:
        if n % cnt  ==  0:
            Largest_prime(n/cnt)
            return 0
        cnt += 1
    print n


Largest_prime(600851475143)

6857

펄입니다
File:ex.pl

use bigint;
for(my$i=2;$i<=$ARGV[0];$i++){
    $ARGV[0]%$i==0 and (push(@primes,$i),$ARGV[0]/=$i,redo)
}
print$primes[-1]

리눅스 셸에서 다음과 같이 사용합니다

$ perl ex.pl 600851475143

6857

Java 재귀함수로 풀었습니다.

import java.util.*;
/**
 *어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 한다.

 예를 들면 13195의 소인수는 5, 7, 13, 29 이다.

 600851475143의 소인수 중에서 가장 큰 수를 구하시오.
 * */
public class Fourth {
    private static ArrayList<Long> list = new ArrayList<Long>();

    public static void main(String [] args){
        long num = 600851475143l;

        findPrime(num);
        System.out.print(list.get(list.size()-1));

    }
    private static void findPrime(long num){
        for(long i = 2l; i<= num; i++){
            if( num%i == 0){
                list.add(i);
                findPrime(num/i);
                break;
            }
        }
    }
}

#include <iostream>
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <map> 
using namespace std;

typedef long long ll;  

map<int,int> prime_factorization(ll n){
    map<int,int> ret; 
    for (int i = 2; i*i <= n; i++){
        while (n%i == 0){
            ++ret[i];  
            n /= i;  
        }
    }
    if (n != 1) ret[n] = 1;  
    return ret; 
}

int main(){
    map<int,int> ans = prime_factorization(600851475143);  
    int maxval = 0;  
    for (map<int,int>::iterator it = ans.begin(); it != ans.end(); it++){
        maxval = max(maxval,it->first); 
    }
    printf("%d\n",maxval); 
    return 0; 
}

C++ 로 고속으로 정답인 6857을 출력합니다.  
제 코드의 시간복잡도는 O(sqrt(n)) 입니다. 

public class LargestPrimeFactor {

    public static void main(String[] args) {
        Long n = 600851475143L;
        for (Long i = 2L; i < n; i++) {
            if (n % i == 0) {
                n = n / i;
            }
        }
        System.out.println(n);
    }
}

Python 3.6

def biggest_prime_factor(n):
    i = 2
    while i*i <= n:
        q,r = divmod(n,i)
        if r == 0:
            n = q
        else:
            i += 1
    return n

결과

>>> biggest_prime_factor(600851475143)
6857
>>> biggest_prime_factor(13195)
29
>>> biggest_prime_factor(4)
2

소수를 찾는 부분을 파이썬 제너레이터로 구현해 보았습니다.

#
# largest prime factor
#

def gen_prime():
    result = []
    i = 1
    while True:
        i+=1
        found = False
        for r in result:
            if i % r == 0: 
                found = True
                break
        if not found:
            result.append(i)
            yield i


def prime_factors(n):
    result = []
    for i in gen_prime():
        if i > n: break
        if n%i==0: result.append(i)
        while n%i==0:
            n = n / i
    return result


print max(prime_factors(600851475143))

JAVA. 단순하게 for문 돌려서 (1씩 증가시키면서) 소인수를 찾았습니다. 한 소인수를 찾은 후에는 그 소인수부터 다시 for문을 돌리구요.

package largestprimefactor;
public class Factorizing {
    public static void main(String[] args) {
        long input=600851475143L;
        long i, r=input, max=1;
        for(i=2;i<=r;i++){
            if(r%i==0){
                /*process*/System.out.print(" "+i);//printing all the factors.
                r/=i;
                if(i>max) max=i;
                i--;
            }
        }
        System.out.println("\nmaxfactor: "+max);
    }
}

Result:

 71 839 1471 6857
maxfactor: 6857

def prime_factor(num):
   '''
   >>> prime_factor(13195)
   5, 7, 13, 29
   '''
   prime = []
   cnt = 2
   while cnt < num + 1 :
      if num % cnt == 0:
         no = num/cnt
         prime.append(cnt)
         num = num/cnt
      cnt += 1
   return prime

print max(prime_factor(600851475143))

primeNum인지 판단하는 함수를 하나 만들고 시작합니다. 2부터 값을 하나씩 증가시켜가면서 주어진 문제의 값을 나누고, 나누어 떨어지면 몫을 다시 problem에 대입합니다. 이값을 다시 2부터 시작하는 divNum으로 나누는 작업을 반복합니다. 이 과정을 반복하여 divNum과 몫이 같아지는 값이 가장 큰 소인수가 됩니다.

import math

problem = 600851475143

def suker_isPrimeNum(n) :
    if n==2 or n==3 or n==5 or n==7 :
        return 1
    elif n%2==0 :
        return 0
    else :
        sqrtNum = int(math.sqrt(n))
        for i in range(3,sqrtNum+1) :
            if n%i==0 :
                return 0

        return 1

divNum = 2
while 1 :
    if problem%divNum == 0 :  # this is not a prime number
        problem /= divNum
        divNum = 2
    else :
        divNum += 1

    if divNum==problem :
        print "Answer : %d"%problem
        break

#python 3.2.5

class PrimeItr:
    def __init__(self, limit, tbl=[2]):
        self.tbl = tbl
        self.limit = limit
    def __iter__(self):
        return self
    def __next__(self):
        prime = self.tbl[-1]
        if prime > self.limit:
            raise StopIteration

        next_prime = prime + 1
        while any(filter(lambda x: not(next_prime % x), self.tbl)):
            next_prime += 1

        self.tbl.append(next_prime)
        return prime, self.tbl

class PrimeFactor:    
    def __init__(self, number):
        self.number = number
        self.ptbl = [2]
    def __iter__(self):
        return self
    def __next__(self):
        NUM = self.number
        for itr,prime_tbl in PrimeItr(NUM, self.ptbl):
            remain = NUM % itr
            if not remain:
                self.number = NUM // itr
                self.ptbl = prime_tbl[:-1]
                return itr
        raise StopIteration


def main():
    l = [itr for itr in PrimeFactor(600851475143)]
    print(l[-1])

C++, XCode 5.1.1로 작성했습니다. 자료형이 저장할 수 있는 숫자의 크기 제한 때문에 C/C++로는 이 문제는 풀기가 확실히 어렵네요. 그래서 GMP 라이브러리(https://gmplib.org)를 사용했습니다.

//
//  main.cpp
//  CodingDoJang-450-CPP
//
//  Created by Chrome-MBPR on 7/10/14.
//  Copyright (c) 2014 cr2025x1. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <gmpxx.h>
#include <list>
using namespace std;

struct prime_factor {
    mpz_class prime_number;
    mpz_class power;
};

int main(int argc, const char * argv[])
{
    mpz_class original_int ("600851475143"); // 미리 주어진 값

    cout << "Searching the largest integer factor in " << original_int << "." << endl;

    mpz_class i;
    mpz_class i_bound (original_int);
    list<prime_factor> known_prime_factor;
    for (i = 2; i <= i_bound; i++) {
        if (i_bound % i == 0) {
            bool is_prime = true;
            mpz_class j_bound;
            j_bound = i / 2;
            for (list<prime_factor>::iterator j = known_prime_factor.begin(); j != known_prime_factor.end(); j++) {
                mpz_class prime_number((*j).prime_number);
                if (prime_number > j_bound) {
                    break;
                }

                if (i % prime_number == 0) {
                    is_prime = false;
                    break;
                }
            }

            if (is_prime) {
                prime_factor newPF;
                newPF.prime_number = i;
                newPF.power = 0;
                while (i_bound % i == 0) {
                    i_bound /= i;
                    newPF.power++;
                }
                known_prime_factor.push_back(newPF);
            }
        }
    }

    for_each(known_prime_factor.cbegin(), known_prime_factor.cend(), [](prime_factor p){cout << p.prime_number << "^" << p.power << endl;});

    cout << "Operation complete." << endl;
    cout << "The largest prime factor of " << original_int << " is " << (*(--known_prime_factor.cend())).prime_number << "." << endl;

    return 0;
}

/*
Searching the largest integer factor in 600851475143.
71^1
839^1
1471^1
6857^1
Operation complete.
The largest prime factor of 600851475143 is 6857.
Program ended with exit code: 0
*/

n=600851475143

def core03(l):
    if l<20:
        return [2, 3, 5, 7, 11, 13, 17, 19]
    SqrtL=int(l**0.5)
    TargetSet =set(range(SqrtL,l))
    TinyPrimeList=core03(int(l**0.5))
    for i in TinyPrimeList:
        TargetSet = TargetSet -set(range(i*2,l,i))
    return sorted(list(set(TinyPrimeList + list(sorted(TargetSet)))))

ResultList=[]
for i in core03(int(n**0.5)):
    if n%i==0:
        ResultList.append(i)

print(ResultList[-1])

python 3.4 기준입니다.

왠지 삽질인것 같지만..

n 의 제곱근보다 작은 prime nuber 를 구해 순환문 돌렸습니다.

prime number 구하는게 시간이 많이 걸리네요..

그래도 acceptable 한 수준입니다.

아무 생각없이 푸는 방법

require 'prime'
600851475143.prime_division.last.first

그래도 좀 고민해 본..

def lagest_prime(n)
  (3...n**0.5).select { |i| (n % i).zero? && i.prime? }.last
end

소수판별함수도 필요 없네요.

주어진수를 N 이라하고, 나누는 수는 d라고 합니다. N을 d로 나눌 수 있을 때까지 거듭해서 나누고 나눌 수 없게 되면 d는 1올려줍니다. 이 과정을 d가 N보다 커질 때까지 반복하면 N이 처음 제시된 수의 가장 큰 소인수가 됩니다.

N, d = 600851475143, 2
while N > d:
  while N % d is 0:
    N //= d
  d += 1
print(N)

Perl

오일러에서 풀땐 이렇게 하고 좋아했었는데..

use integer;
$n=600851475143;
$i=2;
$n/=$i while $n==$n/2*2;
$i--;
while($n>1){
    $i+=2;
    $n/=$i while $n==$n/$i*$i;
}
print $i;

Scala

def largestFactor(n:BigInt):Int = {
  val pf = Stream.from(2).dropWhile(n % _ != 0).head    //prime factor
  if(n == pf) pf else largestFactor(n / pf)
}

2부터 시작해서 나누어지는 첫번째 수를 구하면, 그 수는 항상 소인수입니다. 소인수를 나눈 값으로 재차 그 다음 소인수를 구하면, 마지막으로 구한 소인수가 가장 큰 소인수가 됩니다.

#include "stdafx.h"
#include <iostream>
using namespace std;

bool IsAlone( long long unsigned int nValue )
{
    long long unsigned int nDest = nValue/2;
    for( long long unsigned int i=2; i<nDest; ++i )
    {
        if( nValue % i == 0 )
            return false;
    }

    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
    long long unsigned int value;
    cin >> value;

    long long unsigned int alone = 2;
    long long unsigned int now = value;
    while( 1 < now )
    {
        if( ! IsAlone(alone) )
        {
            ++alone;
            continue;
        }
        if( now % alone != 0 )
        {
            ++alone;
            continue;
        }
        else
        {
            now /= alone;
        }
    }

    cout << alone;
    return 0;
}

c 언어입니다. 6857 입니다.

#include <stdio.h>

long long int main(void)
{
    long unsigned a = 0, b = 600851475143, c = 600851475143, d = 0;

    while(b >= 1)
    {       
        if(600851475143%c==0)
        {
            if(b%c==0)
            {
                for(a = 1; a <= b;)
                {           
                    a++;            
                    if(a < b)
                    { 
                        if(b%a==0)
                            break;
                        else if(a!=b)                   
                            continue;
                    }           
                    if(a==b)
                    {
                        printf("600851475143 의 가장 큰 소인수는 %d 이다.\n", b);
                        d++;
                    }
                }
            }
        }
        if(d!=0)
            break;
        b--;
        c--;
    }       
    return 0;
}

    static long getNextPrime(long prime)
    {
        int chk = -1;
        while (chk != 0)
        {
            chk = 0;
            prime++;
            for (int i = 2; i <= Math.sqrt(prime); i++)
            {
                if (prime % i == 0)
                {
                    chk++;
                    break;
                }
            }
        }
        return prime;
    }

    static void exce63()
    {
        long n = 600851475143L;
        long prime = 2;
        long max = 2;

        while(prime <= Math.sqrt(n))
        {
            prime = getNextPrime(prime);
            if(n%prime == 0 && max < prime)
                max = prime;
        }

        System.out.println(max);
    }

다음 소수를 찾는 함수를 짜서 하나하나 찾아보는식으로 짰습니다.

프로젝트오일러에서 풀었던 문제라, 걍 외부모듈 이용해서 풀어보았습니다. pyprimes는 표준모듈은 아니고 다운로드 가능합니다.

from pyprimes.factors import factorise
print max(factorise(600851475143))

Ruby

largest_prime = ->num,f=2 { num%f==0 ? num=num/f : f=f+1 until num==f; f }
p largest_prime[600851475143] #=> 6857

Time

start = Time.now
l = largest_prime[600851475143]
p "[Max prime factor] : #{l}, #{Time.now - start} sec"

[Max prime factor] : 6857, 0.000352 sec

풀이

* number=600851475143, factor=2
1. factor로 나누어지면 number = number/2 를 반복
2. 나뉘지 않으면 factor를 증가
3. 1~2를 반복했을 때 number와 factor가 동일하면 factor가 답.

6857 C로 제작하였고 openMP를 사용하여 간단하게 소수 구하는 부분 병렬화를 하였습니다.

#include <stdio.h>
#include <omp.h>
#include <string.h>
#include <time.h>

int primeNumber(long long int input)
{
    long long int i = 0;
    int flag = 1;

#pragma omp parallel for
    for(i = 2; i < input; i++)
    {
        if(input % i == 0)      
            flag = 0;
    }

    printf("number: %lld, flag: %d\n", input, flag);
    if(flag == 1)
        return 1;
    else
        return 0;
}

int main(int argc, char *argv[])
{
    long long int num = 600851475143;
    long long int i = 0;
    long long int temp = 0;
    time_t start, end;


    printf("%lld\n", num);

    start = clock();
    for(i = 2; i < num; i++)
    {
        if(num % i == 0)
        {
            printf("now i : %lld\n", i);
            temp = num / i;
            if(primeNumber(temp) == 1)
            {
                //소수라면
                break;
            }
        }
    }

    end = clock();
    printf("%lld 가 가장 큰 소인수 이다.\n", temp);
    printf("elapse Time: %d\n", end - start);

    return 0;
}

C#으로 작성했습니다.

        public void LargestPrimeFactor(long n)
        {
            var value = 2;
            while (value < n)
            {
                if (n%value == 0)
                {
                    LargestPrimeFactor(n/value);
                    return;
                }
                value += 1;
            }
            Console.WriteLine(value);
        }

#파이썬3.5.1
# 수를 입력하면 소인수분해가 되어 나옵니다
#이때 큰 수를 보면 됩니다.
#답:6857
from math import *

def primedp(p):
    dic = {}
    a = p
    for i in range(2, int(sqrt(p))+1):
        c = 0
        while a%i == 0:
            a = a//i
            c += 1
        dic[i]=c
    if a!= 1:
        dic[a] = 1
    dic = list(dic.items())
    for i in range(len(dic), 0, -1):
        if dic[i-1][1] == 0:
            del dic[i-1]
    dic = dict(dic)
    return dic

x = int(input('Input the number...\n>>> '))
print('CACULATING...')
l = list(primedp(x).items())
l.sort()
s = ''
for i in l:
    s += str(i[0])
    if i[1] != 1:
        s += '^'+str(i[1])
    s += ' * '
s = s[:-3]
print('\n' + '='*50 + '\n')
print(x, '=', s)

def f(x):
    n = 2; res = {}
    while 1:
        if x%n == 0:
            if n not in res:
                res[n] = 0
            res[n] += 1
            x /= n
        else:
            n += 1
            if n > x:
                break
    return max(res.keys())

if __name__ == '__main__':
    print(f(600851475143))

파이썬 3.5.1

#카운터 모듈 이용하였습니다.
from collections import Counter
def LPF(x):
    cnt=Counter()
    n=2
    while x> 1:
        while x%n==0:
            cnt[n]+=1
            x = x//n
        n += 1
    a=list(cnt.keys())
    a.sort()
    return a[-1]



if __name__=='__main__':
    print(LPF(600851475143))

def prime_factor(n):
    if not(n > 2):
        return []
    i = 2
    while True:
        while n % i == 0:
            n /= i
            yield i
        if n == 1:
            break
        i+=1

print(max(prime_factor(600851475143)))

Python 3.5.2에서 작성하였습니다.

def chk_sosu(num):
    for x in range(2,num):
        if num % x == 0:
            return False
    return True

n, x = 600851475143, 1

while n != 1:
    x += 1
    if chk_sosu(x) and n % x == 0:
        n = n//x
print(x)

#### 2016.12.31 D-418 ####

노가다 코드 허허

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void main() {
    double max = 0;
    double n =  600851475143;
    for(double i=1;i<n;i++) {
        if(fmod(n,i)==0) {
            int c = 0;
            for(double j=1;j<=i;j++) {
                if(fmod(i,j)==0)
                    c++;
            }
            if(c==2)
                if(max < i)
                    i = max;
        }
    }
}

max([i for i in range(2,600851475143/2+1) if n%i==0 and sum(1 for j in range(2,i) if i%j==0)==0])

소수 구하기 ```{.java} package sss; /* * 소수 구하기 : http://marobiana.tistory.com/89 * 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 한다.

예를 들면 13195의 소인수는 5, 7, 13, 29 이다.

600851475143의 소인수 중에서 가장 큰 수를 구하시오.*/ import java.util.LinkedList;

public class Largest_Prime_factor { LinkedList prime; long a = 600851475143L;

public Largest_Prime_factor(){
    prime = new LinkedList<Integer>();
    prime.add(2);
}

public void find(){
    if(a % 2 == 0)
        a /= 2;
    for(int i = 2; a != 1;i++){
        for(int j = 0; j < prime.size(); j++){
            if(i % prime.get(j) == 0)
                break;
            else if(j+1 == prime.size()){
                prime.add(i);
                if(a % i == 0){
                    a /= i;
                }
            }
        }
    }

    System.out.println(prime.peekLast());
}

}

```> 소수를 구하는 방법은 위의 링크에 나와있는 방법을 사용했습니다.

파이썬 3.5.3 연습용 코드입니다.

def fmaxnum(n):
    result=[]
    x=2
    while 1>0:

        if n == x:
            result.append(x)
            print(result)
            break

        elif n%x == 0:
            result.append(x)
            n = n/x
            x = 2
        elif n%x != 0:
            x=x+1

다음 단계들을 계속 반복한다

• 소인수들을 작은 수부터 찾아낸다

• 현재 수를 찾은 소인수로 나눈다.

• 결과가 1 이면 반환한다 (1이란 말은 모든 소인수를 이용해 입력된 값을 나눴다는 뜻 )

def f( n ):
    resList = []    
    while True:
        for i in range(2, n+1):
            if n % i == 0:
                resList.append(i)
                n //= i
                break
        if n == 1:
            return resList

print( f(600851475143)[-1])

// 600851475143의 소인수분해 - C#
using System;

namespace VERYBIG
{
    class Program
    {
        static void Main(string[] args)
        {
            long n = 600851475143;
            long answer = 0;
            for (int i = 2; i < 100000; i++) // 적당한 숫자 지정
            {
                int counter = 0;
                for (int j = 1; j <= i; j++)
                    if (i % j == 0)
                        counter++;
                if (counter != 2)
                    continue;
                if (n % i == 0)
                    answer = i;
            }
            Console.WriteLine(answer);
            // 답은 6857
        }
    }
}

소수로 나누어 떨어지는 것만 체크하면 됩니다. for i 사이클에 n을 그대로 박으면 결과 출력이 너무 늦어져서 적당한 숫자를 넣었습니다.

답은 6857이네요.

def primeFactor(num):
    if num == 2 or num == 3:
        return num
    else:
        while 1:
            for x in range(2,int(num/2)+1):
                if num % x == 0:
                    num = num+1
                    break;
            if x == int(num/2):
                return num


num = 600851475143

pF = 2
while 1:
    if pF == num:
        break
    elif num % pF == 0:
        while num % pF == 0:
            num = int(num/pF)
    else:
        pF = primeFactor(pF+1)


print("최대 소인수:  ",pF)

아이디어

1. 2를 제외한 모든 소수는 홀수

2. x로 나눌 때는 n/x 까지만 검사하면 된다

라는 점에 착안하여 다음 코드를 작성하였습니다.

javascript

var div = function(n, i) {
    while (n % i === 0) {
        n /= i;
    }
    return n;
};

var getLargestPrimeFactor = function(n) {
    n = div(n, 2);

    for (var i = 3; i <= n / i | 0; i = i + 2) {
        n = div(n, i);
    }

    return n;
};


console.log(getLargestPrimeFactor(600851475143));

>>> 6857

def lpf_rec(n, f):
    if n == 1: 
        return f    

    while n % f > 0: 
        f += 1

    return lpf_rec(n // f, f)

print(lpf_rec( 600851475143 , 2))

그냥 짰다가 다른 답 보고 재귀로 바꿔 봤습니다.

저도 처음에 깜박했는데, 소인수 찾은 다음에 안 나눠질 때까지 나눠야 하지 않는지?

많이들 빼먹으신 거 같습니다.

num = int(input("숫자를 입력하세요: ")) 
x = 2
num_list = []
while x <= num:
    if num % x == 0:
        num_list.append(x)
        num = num / x
    else:
        x += 1
print(num_list[-1])

이제 막 시작한 학생입니다. 이상한 점이나 더 좋게 고칠점이 있으면 지적 부탁드립니다.

이상하지만 저장

list = []
while True:
    for x in range(2,number+1):        
        if number % x == 0:
            number = number // x
            list.append(x)
            break
    if number == 1:
        print(list[-1])
        break

public class LargestPrimeFactor {
    public static void main(String[] args) {
        System.out.println(isLargestFactor(600851475143l,2));
    }

    public static long isLargestFactor(long n, long i) {
        if(n>i) {
            if(n%i==0) return isLargestFactor(n/i, i);
            return isLargestFactor(n,i+1);
        }
        return n;
    }
}

C

#include <stdio.h>

int isPrime(int input);
int main()
{
    long sosu = 600851475143;
    int a=2;
    int b=0;
    long total=1;
    int tmp=0;
    while(total!=sosu)
    {
        if(isPrime(a)==0)
        {
            if(sosu%a==0)
            {
                printf("prime a : %d\n", a);
                tmp = a;
                total = total*tmp;
                printf("total : %ld\n",total);      
                b = sosu/a;

            }

        }
        a++;
    }
    printf("MAX PRIME : %d\n",a);   
    return 0;
}

int isPrime(int input)
{
    for(int i=2;i<input;i++)
    {
        if(input%i==0)
            return 1;
    }
    return 0;
}

# 소수인지 아닌지 구별하는 함수 *****
def if_primenumber(n) :

    if n == 1 :
        return False

    else :

        dividers = []
        for i in range(2, n + 1) :
            if n % i == 0 :
                dividers.append(i)

        if len(dividers) > 1 :
            return False

        elif len(dividers) == 1 :
            return True

# 여기부터 문제풀이 *****

a = 600851475143

a_dividers = []
a_primenumbers = []

for s in range(1, a + 1) :
    if a % s == 0 :
        a_dividers.append(s)

for f in a_dividers :
    if if_primenumber(f) == True :
        a_primenumbers.append(f)

print(a_primenumbers[-1])

소인수분해 자체가 컴퓨터에게 매우 힘든 일이긴 하죠 오죽하면 현재 제일 강력한 암호 체계가 소인수분해를 이용한 것이겠습니까 수가 커질수록 연산량이 엄청나게 많이 늘어날듯...

prime=raw_input('User Input:')
prime=int(prime)
multi=1
a=1

while multi<prime:
    for i in xrange(2,int(prime/2)):
        if prime%i==0:
            if i==2 or i==3:
                b=i
                multi=a*b
                a=multi
                print(i)
                if multi==prime:
                    print('Largest prime is %d'%i)
                    break
            elif i%2!=0 and i%3!=0:
                b=i
                multi=a*b
                a=multi
                print(i)
                if multi==prime:
                    print('Largest prime is %d'%i)
                    break

arr = []
def f(n):
    if n <= 1:
        print(max(arr))
        return True
    for i in range(2,n+1):
        if n%i == 0:
            arr.append(i)
            f(n//i)
            break
f(13195)
f(600851475143)

C++입니다~

#include <iostream>
#define element long long
using namespace std;

element sosu_max(element num) {
    element max = 0;
    element flag = num;
    for (element i = 2;i < flag; i++) {
        if (num%i == 0) {
            num /= i;
            if (i > max) max = i;
            //cout << num << " @@ " << max << endl;
            i = 2;
            if (num == 1) break;
        }
    }

    return max;
}

int main() {

    element num = 600851475143;
    cout << sosu_max(num) << endl;


    return 0;
}

def cal(n):
    start=2
    while start<n//2:
        if not n%start:
            return(cal(n/start))
        start+=1
    else: return(int(n))

num=600851475143
print(cal(num))

n = 600851475143
# 재귀함수
def Largest_prime(n):
    num = 2
    while num <n :
        if n%num == 0 :
            Largest_prime(n/num)
            return 0
        num +=1
    print(n)
Largest_prime(n)

a=600851475143
c=[]
while True:
    for n in range(2,a+1):
        if a%n==0:
            c.append(n)
            a=a//n
            break
    if a==1:break 
print(max(c))        

a = input("소인수 분해할 숫자를 입력해 주세요")
b = int(a)
c = ()
d = 2
while d <= b:
       if b % d == 0:
              c += (d,)
              b = b/d
       else:
              d += 1

e = len(c)
f = int(e)
print("x".join(str(x) for x in c))

어떤분의 도움을 받았네요. x를 표기하는 법을 몰라서....

파이썬 3.6

def primefactor(x):
    m = 2
    factor =[]
    factor2 = []
    factorset = {}
    result = []
    while x >= m:
        if x%m == 0:
            factor.append(m)
            x = x/m
        m += 1
    if int(x%m) != 1 :
        factor.append((int(x%m)))
    for i in factor:
        m = 2
        while i >= m:
            if i%m == 0:
                factor2.append(m)
                i = i/m
            m += 1
        if int(i%m) != 1:
            factor2.append((int(i%m)))
    factorset = set(factor2)
    for i in factorset:
        if len(factor) == len(factorset):
            result = factor2
        else:
            result.append(i**factor2.count(i))
    print(result, "최대값은 = %d"% max(result))

*결과값

[71, 839, 1471, 6857]  최대값은 =  6857

# 파이썬

input_data = 600851475143


def largest_prime(i, j=2):
    while j < i:
        if i % j == 0:
            return largest_prime(i/j, j)
        else:
            if j == 2:
                j = 3
            else:
                j += 2
    return i


print(largest_prime(600851475143))

import math
def prime(n):
    m = int(math.sqrt(n))
    a = [n%i for i in range(2,m+1)]
    return all(a)


def largestprimefactor(n):
    if prime(n):
        return n
    else:
        m = int(math.sqrt(n))
        for i in range(2,m+1):
            if n%i == 0:
                return max(largestprimefactor(i), largestprimefactor(n//i))

print(largestprimefactor(600851475143))

def isPrime(n):
    if n<2:
        return False
    if n==2:
        return True
    for k in range(3,int(n**0.5)+1,2):
        if n%k==0:
            return False
    return True

num=600851475143
for k in range(3,int(600851475143**0.5)+1,2):
    if isPrime(k)==True and num%k==0:
        if isPrime(int(num/k))==True:
            print(int(num/k))
            break
        num=int(num/k)

n,d=600851475143,2
while d<n:
    while n%d==0:
        n=n/d
    if n==1 : break
    d=d+1
print(d)

public class hello {
    public static void main(String[] args) {
        long input=600851475143L;
        long i, r=input, max=1;
        for(i=2;i<=r;i++){
            if(r%i==0){
                r/=i;
                if(i>max) max=i;
                i--;
            }
        }
        System.out.println("\nmaxfactor: "+max);
    }
}

Swift입니다. 재귀호출 없이 풀었습니다.

import Foundation

func getMaxPrimeFactor(_ givenNumber: Int) -> Int {
    var number = givenNumber
    var divider = 2
    var maxDivider = 0
    while divider < number {
        if number % divider == 0 {
            if number / divider == 1 {
                break
            } else {
                number /= divider
                divider = 2
            }
        } else {
            divider += 1
            if maxDivider < divider {
                maxDivider = divider
            }
        }
    }
    return maxDivider
}

print( getMaxPrimeFactor(600851475143) )

실행결과는...

6857

def prime_number3(num):
    cnt = 2
    a, b = 0, 0
    while num != cnt:
        a, b = divmod(num, cnt)
        if b == 0 : num = num / cnt
        if b != 0 : cnt = cnt + 1
    print(int(cnt))


prime_number3(13195)

// 자바입니다
public static void main(String[] args) throws Exception {       
          long n = 600851475143L;
            for (long i = 2L; i < n; i++) {
                if (n % i == 0) 
                    n /= i;
            }
            System.out.println(n);
    } // 인수가 나오면 n을 인수로 나누고 또 나누다가 안 나눠지면 출력하는 식으로 풀었습니다

def largest_p(n):
    i = 2
    while i < n:
        if not n%i:
            while not n % i: n /= i
        i += 1
    return int(n)

print(largest_p(600851475143))

import java.util.ArrayList;
import java.util.List;

public class LargestPrimeFactor {

    public static List<Long> getPrimeValues(long number){ // number 보다 작은 소수 리스트 구하기

        List<Long> primeValues = new ArrayList<>();
        if(number > 2){
            primeValues.add(new Long(2));
        }else{
            return null;
        }

        for(int i = 3; i< number; i=i+2){
            boolean primeFlag = true;
            for(int j = 0; j < primeValues.size(); j++){
                if(i % primeValues.get(j) == 0){
                    primeFlag = false;
                    break;
                }else{
                    continue;
                }
            }
            if(primeFlag){
                System.out.println(i);
                primeValues.add(new Long(i));
            }
        }

        return primeValues;

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long number = 600851475143L;

        List<Long> primeList = getPrimeValues(number);

        for(int i = primeList.size()-1; i >= 0; i--){
            if(number % primeList.get(i) == 0){
                System.out.println(primeList.get(i));
                break;
            }
        }

    }

}

2 이상의 수로 계속 나눠, 나눠떨어지는 수를 구합니다. 기존 수 / 얻은 수 를 한 후 이 값을 같은 방법으로 돌려줍니다. 소인수는 1을 제외하고는 나눠떨어지지 않기 때문에 가장 큰 소인수만 남게 됩니다. 훨씬 더 큰 수도 1초 내로 구해집니다.

public class Largestprimefactor {
    public static void main(String[] args) {
        long num = 600851475143123L;
        num = a(num);
        System.out.println(num);
    }

    private static long a(long num) {
        for (long i = 2; i < (num + 1) / 2; i++)
            if (num % i == 0)
                num = a(num / i);
        return num;
    }
}

public class Main {
    public static void main(String[] args) {
        long num=600851475143l;

        large_prime(num);
    }

    private static void large_prime(long num) {
        for(long i=2;i<num;i++) {
            if(num%i==0) {
                num=num/i;
                large_prime(num);
                break;
            }else if(i==num-1) {
                System.out.println(num);
            }
        }
    }
}

def soinsu_max(a, s=2):
    for i in range(s,a+1):
        if a%i == 0 :
            a //= i
            if a==1:
                return i
            else:
                return soinsu_max(a, i)


print(soinsu_max(600851475143))

def soinsubunhae(n):
    for i in range(2, int(n**0.5)+1):
        if n%i == 0: return [i] + soinsubunhae(n//i)
    return [n]

print(max(soinsubunhae(600851475143)))

6857

import math

def prime_factor(i) :
    #소수는 2부터 시작
    max_num=2
    num=i
    cnt=0
    for n in range (2, int(math.sqrt(i))+1) :
        if n*n > num :
            break
        elif num%n==0 :            
            num=num//n
            max_num =num
        cnt+=1
    return cnt

def prime_factor(n):
    if n == 1: return []
    else:
        result = []
        for search in range(2, int(n ** (1/2)) + 1):
            if n % search == 0:
                result.append(search)
                break
        if not result: result.append(n)
        result.extend(prime_factor(n // result[0]))
        return result
print(max(prime_factor(600851475143)))

입력된 수의 소인수들을 리스트로 리턴하는 소인수분해 함수를 정의한 뒤 결과의 max값을 출력하는 코드입니다

def func():
    global sosu, N
    result=[]
    N = int(input('소인수분해할 자연수'))
    sosu=2
    while sosu <= N:
        if N%sosu ==0:
            result.append(sosu)
            N =N/sosu
        else:
            sosu = sosu+1
    print(result[-1])
func()

from math import sqrt
n = 3
big_n = 600851475143
box = []
while big_n != 1 :
    for i in range(2, int(sqrt(n))+1) :
        if n%i == 0 :
            break
    else :
        while big_n%n==0 :
            big_n = big_n//n
            box.append(n)
    n+=1
print(max(box))

C#

using System;

namespace CD063
{
    class Program
    {
        static void Main()
        {
            long result = GetMaxPrimeFactor(600851475143);
            Console.WriteLine(result);
        }

        static long GetMaxPrimeFactor(long number)
        {
            long maxPrimeFactor = 0;
            long targetValue = number;
            long checkValue = 2;
            while (checkValue*checkValue <= targetValue)
            {
                if (targetValue % checkValue == 0)
                {
                    maxPrimeFactor = checkValue;
                    while (targetValue % checkValue == 0) { targetValue /= checkValue; }
                }
                else { checkValue++; }
            }
            if (targetValue > maxPrimeFactor) { maxPrimeFactor = targetValue; }

            return maxPrimeFactor;
        }
    }
}

6857

def Largest_prime_factor(num):
    d = 2
    while d < num:
        if num % d == 0:
            num = Largest_prime_factor(num/d)
        else:
            d += 1
    return int(num)

print(Largest_prime_factor(600851475143))

# 소수인지 아닌지 판별

def is_prime(number):
  if number > 1:
    if number == 2:
      return True
    if number % 2 == 0:
      return False
    for current in range(3, int((number ** 0.5) +1), 2):
      if number % current == 0:
        return False
    return True
  return False

## 소수 제너레이터
def get_primes(input_list):
  return (element for element in input_list if is_prime(element))

## 소인수분해
def get_factors(number):

  factors = []
    for p in get_primes((x for x in range(int(number ** 0.5 + 1)))):
      count = 0
      while number % p == 0:
        number /= p
        count += 1
      if not count == 0:
        factors.append((p, count))
        if is_prime(number):
          factors.append((int(number), count)
          return factors
  if len(factors) == 0:
    factors.append((number, 1))
    return factors

c = time.time()
print(get_factor(600851475143))
print(time.time()-c)

[(71, 1), (839, 1), (1471, 1), (6857, 1)]
0.002722024917602539

# 제너레이터 이용

# 소수인지 아닌지 판별 함수
def is_prime(number):
  if number > 1:
    if number == 2:
      return True
    if number % 2 == 0:
      return False
    for current in range(3, int(number ** 0.5) + 1, 2):
      if number % current == 0:
        return False

    return True

  return False
# 소수 생성 제너레이터
def get_primes(num):
  yield 2
  yield from (x for x in range(3, int(num**0.5+1),2 ) if is_prime(x))
num = 600851475143
k = get_primes(num)

#최대 소인수 찾기
def largest_prime(num):

  d = next(k)
  while d < num:
    if num % d == 0:
      num = largest_prime(int(num / d))
    else:

      d = next(k)

  return int(num)

정수 n의 소인수를 구하기위해 2부터 차례대로 나누어 본다. 나누어진다면 그 수를 소인수 리스트에 추가하고 다시 똑같은 수로 나누어 본다. 나뉘어지지 않는다면 다음 수로 넘어가서 똑같은 작업을 반복한다. 소인수의 크기는 루트 n을 넘지 않기 때문에 나누는 수의 최대값을 루트 n으로 설정한다. 인자 n이 소수일 경우 속도에서 차이가 많이 난다.

from math import *

def Factor(n):
    L = list()
    i = 2
    Max = sqrt(n)
    while i <= Max:        
        if n%i == 0:
            L.append(i)
            n = n // i
        else:
            i += 1
    if n != 1:
        L.append(n)
    print(L[-1])
    return L        

Factor(600851475143)

def LPF(N):
    wari=2
    while wari<N:
        if N%wari==0:
            return LPF(int(N/wari)) 
        wari+=1
    return N

print(LPF(int(input())))

문제에서는 이미 특정한 수를 상정하고서 풀도록 하였지만, 모처럼이니 사용자가 직접 입력하여 다양한 수의 최대소인수를 알 수 있도록 작은 변화를 주었읍니다. 다만, 맨 처음 작성한 코드에서는 기저사례를 지정해야 할 필요가 있었지만 나누는 인수wari를 어디서 조작하는냐에 따라서 굳이 기저사례를 따로 지정 해 둘 필요가 없음을 알게되었읍니다. 하지만 이후에 임의의 수를 입력하여 보았더니, 대략 1092287033 정도의 수를 입력 했을 때, 결과가 엄청나게 안 나오더군요. 혹시 잘못 짠건가 하여 이것저것 바꾸어보고 하여보았지만, 왜인지 느린것은 고사하고 결과가 아예 안나왔읍니다. 그래서 혹시 이것이 엄청나게 큰 소수여서 그래서 안 나오는건가 하여, 본 알고리듬에서도 수학적인 꼼수가 있지만은 결국에는 완전탐색법에 기초하여 문제를 풀고 있으므로 똑같은 시간복잡도를 갖는 완전탐색법으로 1092287033을 2부터 시작하여 일일히 나누는 조작을 반복문으로 실시, 만일 나누어 떨어질 경우, 특별한 문장을 출력하도록 하는 간단한 코드를 짜고 실행 시켜본 결과, 아직까지 결과가 나오지를 않는군요. 더 조사를 해보고 싶지만.... 문제에서 원하는 답은 600851475143의 최대소인수이고... 슬슬 배도 고프고..저녁밥을 먹으러 가야겠읍니다.^^;;

a = 600851475143
b = 0
for i in range(a):
    if a %% i == 0:
        b = i
        a = a % i
    if a < i:
        print(b)
        break   

코딩 초보자 입니다! 틀린거 있으면 알려주세요! -Made by Ethan Baliey

def isprime(n):
    if n <= 1: return False
    elif n == 2: return True
    else:
        for i in range(2, n):
            if n%i == 0: return False
        return True

def cds(n):
    return [x for x in range(1, n+1) if n%x == 0]

def prime_factor(n):
    p = []
    a = cds(n)

    for i in range(len(a)):
        if isprime(a[i]): p.append(a[i])

    print(p[-1])

600851475143에 대한 답은 못구했습니다.. 답이 금방 안나오네요.. 제가 잘못 푼걸까요??

초보입니다.. 소수인지 판단하는 함수 만들고 소인수들 중 가장 큰 것을 출력하는 함수를 만들었습니다..

import math


def IsPrime(x): 
    h = math.sqrt(x)
    m = math.ceil(h)
    for i in range(2, int(m)):
        if x % i == 0:
            return False
    else: return True


def LarPrimeFac(N):
    h = math.sqrt(N)
    m = math.ceil(h)
    key = 0
    for x in range(2,int(m)):
        if N % x == 0 and IsPrime(x) and x > key:
            key = x
    return key

def prime_factor(a):
    i = 3
    while i < a:
        if a%i == 0:
            a = a/i
            i = 1
        i += 2
    print(a)

prime_factor(600851475143)

python 3.7

def LPF(n):
    a = 2
    while 1:
        if a**2 > n:
            return n
        elif n % a == 0:
            n //= a
            #여기에 print(a) 를 추가하면 소인수분해도 가능하다.
        elif a == 2:
            a = 3
        else:
            a += 2

import java.util.ArrayList;

public class LargestPrimeFactor {

    public static void main(String[] args) {
        ArrayList<Long> list = new ArrayList<Long>();
        int BiggestNumber = 0;
        long count = 1;
        long num = 600851475143L;
        for(int i=0;;i++) {
            for(long j=2;;j++) {
                if(num%j==0) {
                    num=num/j;
                    list.add(j);
                    if(BiggestNumber<j) {
                        BiggestNumber=(int) j;
                        count=count*(int)j;
                    }
                    break;
                }
            }
            if(count>=600851475143L) {
                break;
            }
        }
        System.out.println(list);
        System.out.println(BiggestNumber);
    }
}

//소인수랑 그 중 제일 큰 수를 찾았습니다.
//저같은 경우는 24를 소인 수 분해하면 2x2x2x3이라서 이 숫자도 중복된 소수가 있을 수 있다 생각해서 이렇게 풀었습니다..막상 중복된 소수는 없었지만..

n, d, result = 600851475143, 2, []

while d!= n :
    for s in range(1, d) :
        if d % s == 0 and s != 1 :
            break
        if s == d-1 and n%d == 0 :
            result.append(d)
            while n %d == 0 :
                n = n/d
    d +=1
result.append(int(n))
print(max(result))

단순하게 소수를 찾아낸 뒤, 600851475143이 소수로 나누어 떨어지면 나누어 떨어질 때 까지 나누고 다음 소수를 찾는 방식으로 계산했습니다.

결과

6857

n=int(input("숫자 n을 입력하십시오:"))
elst=[]
for i in range(1,int(n**(1/2))+1): #입력한 n의 공약수 찾기
    if n%i==0:
        elst.append(i)
        elst.append(n//i)

for num in sorted(elst): #입력한 n의 공약수 리스트를 정렬하여 그 중 소수가 아닌 수를 빼기
    for k in range(2,int(num**(1/2))+1):
        if num%k==0:
            elst.remove(num)
            break
print(max(sorted(elst))) #6857

python 3.6

a = int(input())
d = []
i = 2
while a > 1:
    if a % i == 0:
        b = i
        c = a/b
        a = c
        d.append(b)
    else:
        i = i+1
d = list(set(d))            
print(max(d))  

def prime(num):
    prime_number = []
    for i in range(2, num+1):
        while num % i == 0:
            num /= i
            prime_number.append(i)
    return max(prime_number)

def main():
    num = 600851475143
    print(prime(num))

if __name__ == '__main__':
    main()

n = 600851475143
i = 2
factor_list = []
while True:
    if n % i == 0:
        n = n / i
        factor_list.append(i)
        i = 2
        continue
    elif n < i:
        break
    i+=1
print(max(factor_list))

def sosu(num):
    for i in range(2,num):
        if num%i==0:
            return 0
    return 1

num=600851475143
list_a=[]
for i in range(2,num+1):
    if num==1:
        break
    so=sosu(i)
    if so==1 and num%i==0:
        list_a.append(i)
        num=num/i
print(max(list_a))

#파이썬

#처음에 프로그램을 무식하게 짰더니 몇시간을 기다려도 계산중이더니
#다시 좀더 간결하게 짰더니 600851475143의 결과가 
#예전 방식으로 짠 코드의 13195 결과보다 훨씬 더 빨리 나오네요 
#어떻게든 결과는 나오겠지만 어떻게 짜느냐에 따라 시간차가 너무나도 크다는 것을 느끼게 해준 문제입니다

a=int(input('num?'))
i,max=2,0
while(i<=a):

    if a%i==0:
        a/=i
        if i>max:
            max=i
    else:
        i+=1

print (max)

def Largest_prime_factor(n):
    cnt = 2
    while cnt < n:
        if n % cnt  ==  0:
            Largest_prime_factor(n/cnt)
            #나누어떨어지면 다시 cnt = 2
            return 0
        cnt += 1
    print(n)

def primeFactor(n):
    factor = []
    for i in range(2, n):
        if n % i == 0:
            factor.append(i)
            if n == i:
                break
            n = int(n/i)
            continue
    print(max(factor))


primeFactor(13195)
primeFactor(600851475143)

def Largest_prime_factor(number):

  for_answer=[]

  while number>1:

    for i in range(2,int(number)+1,1):

      if number%i==0:

        if i not in for_answer:

          for_answer.append(i)

        number=number/i

        break

  return max(for_answer)

print(Largest_prime_factor(13195))

print(Largest_prime_factor(600851475143))

def sosu(num):
    temp = []
    for i in range(1, num+1):
        if num % i == 0:
            temp.append(i)
    if len(temp) == 2:
        return True

def func1(num):
    temp = []
    temp_num = num
    while temp_num > 2:
        for i in range(1,temp_num+1):
            # print(i,'th round')
            if sosu(i) and (temp_num % i == 0):
                temp.append(i)
                temp_num = temp_num // i
                print(i, temp_num)
            if temp_num == 1:
                break

    return print(temp, max(temp))


func1(600851475143)

python 3.8.7

def largest_prime_factor(n):
    fact = []
    i = 2
    while i<=n:
        if n%i==0:      
            fact.append(i)
            n//= i
        else:
            i+=1
    return fact[-1]

600851475143을 대입하면 다음과 같습니다.

>>> largest_prime_factor(600851475143)
6857

def largest_prime_factor(n):

    def prime(x):
        for i in range(2, x):
            if x % i == 0:
                return False
        return True

    prime_list = [i for i in range(2, n) if n % i == 0 and prime(i)]
    result = max(prime_list)
    return result

def Factors(n):
    count = 2
    while count < n:
        if n % count  ==  0:
            Factors(n/count)
            return 0
        count += 1
    print (n)


Factors(600851475143)

def soin(n):
    i = 2
    while n > i:
        while n%i == 0:
            n //= i
        i += 1
    return print(n)

soin(600851475143)

#codingdojing_largest prime factor_re

#1 나눠서 찾기. 2부터 시작하여, 나눠서 남은 값을 다시 처음부터 2부터 나눈다.

from math import sqrt

n = 600851475143
i = 2

while n:
    if i == n: 
        print(n); break 
    elif n % i == 0:
        n //= i; i = 2
    else: i += 1 

#2 recursive

def LPF(n):

    i = 2
    while i < sqrt(n):      #사실 root(n) 이상 넘어갈 필요가 없다.
        if n%i == 0: return LPF(n//i)
        else: i += 1

    print(n)

LPF(600851475143)   #6857

def Largest_prime_factor(s):
    a = 2
    while a < s:
        if s%a == 0:
            s = s//a
        a += 1
    return s


if __name__ == '__main__':
    s = int(input())
    print(Largest_prime_factor(s))

a = 600851475143
n=2
arr =[]
while a!=1 :
    if a%n==0:
        a //=n
        arr.append(n)
    else:
        n +=1


print(max(arr))

// Rust

fn largest_prime(n_: u128) -> u128 {

let mut n = n_;
let mut k = 2;
loop {
    if n % k == 0 {
        n /= k;
        if n < k { break; }
        k = 1;
    }
    k += 1;
}
k

}

[test]

fn test() {

assert_eq!(largest_prime(13195), 29);
assert_eq!(largest_prime(600851475143), 6857);

}

import sympy
from sympy.ntheory import factorint

n=600851475143

print(max(factorint(n).keys()))

def LPF(N):
    pn = 2
    pn_list = []
    while N != 1:
        if N % pn == 0:
            N = N / pn
            pn_list.append(pn)
        else:
            pn += 1
    return max(pn_list)

def largestPrime(num):
    n=2
    while n*n<num:
        if num%n==0:
            while num%n==0:
                num //= n
        n += 1

    return num

print(largestPrime(600851475143))
print(largestPrime(111))