Das deutsche Python-Forum

Code: Alles auswählen

import java.util.*;

public class PrimeCalculator {
    
    public static List<Integer> getPrimes(int limit) {
        List<Integer> primes = new ArrayList<Integer>();
        if (limit < 2) {
            return primes;
        }
        primes.add(2);
        
        for (int i = 3; i <= limit; i += 2) {
            boolean isPrime = true;
            for (int prime : primes) {
                if (i % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(i);
            }
        }
        return primes;
    }
    
    public static int getLargestPrimeFactor(int n) {
        if (n < 2) {
            throw new IllegalArgumentException("n must be >= 2");
        }
        List<Integer> candidates = getPrimes(n / 2);
        Collections.reverse(candidates);
        
        int result = -1;
        for (int candidate : candidates) {
            if (n % candidate == 0) {
                result = candidate;
                break;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(getLargestPrimeFactor(111));
    }
}

Code: Alles auswählen

# input %rax = number to factor
# output %rax = largest prime factor
primfac:
        movq $2, %rcx
        jmp _start
_loop:
        xorq    %rdx, %rdx
        divq    %rcx
        orq     %rdx, %rdx
        jne     _cont
_start:
        cvtsi2sdq       %rax, %xmm0
        sqrtsd  %xmm0, %xmm0
        cvttsd2siq      %xmm0, %rdi
        movq    %rax, %rsi
        jmp     _test
_cont:
        incq    %rcx
        movq    %rsi, %rax
_test:
        cmpq    %rdi, %rcx
        jle     _loop
        ret

Code: Alles auswählen

public class PrimeCalculator {
    
    public static int getLargestPrimeFactor(int n) {
        while (n % 2 == 0) {
            n /= 2;
        }
        int result = 2;
        for (int i = (int) Math.sqrt(n); i < n; i++) {
            double j = Math.sqrt(i * i - n);
            if (j == (int) j) {
                // Quadratzahl gefunden
                result = i + (int) j;
                break;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(getLargestPrimeFactor(486847));
    }
}

Code: Alles auswählen

#!/usr/bin/env node
'use strict';
var _ = require('underscore');

var createPrimeGenerator = function () {
    var primes = [2];
    var candidate = 1;
    var testCandidate = function (prime) { return candidate % prime != 0; };
    var next = function () {
        next = function () {
            while (true) {
                candidate += 2;
                if (_(primes).every(testCandidate)) {
                    primes.push(candidate);
                    return candidate;
                }
            }
        };
        return 2;
    };
    return function () { return next(); };
}

var factor = function (n) {
    var result = [];
    var getNextPrime = createPrimeGenerator();
    while (n > 1) {
        var prime = getNextPrime();
        if (n % prime == 0) {
            result.push(prime);
            while (n > 1 && n % prime == 0) n /= prime;
        }
    }
    return result;
}

var main = function () {
    console.log(factor(parseInt(process.argv[2])));
};

main();

Code: Alles auswählen

if all(a%x>0 for x in prime_proof): ...

Code: Alles auswählen

primteiler = [2]

n = int(input("Gib eine ganze Zahl ein: "))

a = 3
        
while a <= n/2:
    if all(a%x > 0 for x in primteiler) and n%a == 0:
            primteiler.append(a)
    a = a + 2
print(primteiler)

Code: Alles auswählen

from itertools import count, takewhile

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    for candidate in takewhile(lambda i: i <= n, count(2)):
        while n % candidate == 0:
            n /= candidate
    return candidate

Code: Alles auswählen

from itertools import count, takewhile, chain

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    sqn=n**0.5
    for candidate in takewhile(lambda i: i <= sqn, chain((2,), count(3, 2))):
        while n % candidate == 0 and n>candidate:
            n /= candidate
            sqn=n**0.5
    return n

Code: Alles auswählen

from itertools import chain, count, takewhile

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    sqn = n**.5
    candidates = chain([2], count(3, 2))
    for candidate in takewhile(lambda i: i <= sqn, candidates):
        while n % candidate == 0:
            n /= candidate
        sqn = n**.5
    return candidate

Code: Alles auswählen

from math import sqrt

def prime_factors(n):
    sq_n = sqrt(n)
    counter = 0
    candidate = 2
    while candidate <= sq_n:
        while not n % candidate:
            n /= candidate
            sq_n = sqrt(n)
            counter += 1
        if counter:
            yield (candidate, counter)
            counter = 0
        if candidate == 2:
            candidate += 1
        else:
            candidate += 2
    if n > 1:
        yield (n, 1)

def pprint_factors(factors):
  return ' * '.join('%d^%d' % (b, e) if e > 1 else '%d' % (b,)
                    for b, e in factors)