Das deutsche Python-Forum

Code: Alles auswählen

def prime_factors(num):
    result=[]
    for k in (2,3,5):
        while num%k==0: num //= k; result.append(k)
    sqn=int(num**0.5)
    k=7
    while k<=sqn:
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 4
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 6
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 2
        while num%k==0: num //= k; sqn = int(num**0.5); result.append(k)
        k += 6
    if num!=1:
        result.append(num)
    return result

Code: Alles auswählen

primteiler = [2]        

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

a = 3

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

if n%2 > 0:
        primteiler.remove(2)
print("Erste Primfaktoren bis 1'000'000: ",primteiler)                          

# nur falls grösster gefundener Primfaktor < n**0.5:

if primteiler[-1] < n**0.5:        
        
        p = 1
        for i in primteiler:
            p *= i
        print("Produkt Primfaktoren bis 1'000'000 = ", p)

        print("n durch Produkt: ",n/p)  

        if n/p == 1:
            print("Das waren alle Primfaktoren von n")
        else:
            if n/p < 10000000:
                print("Die restlichen kommen gleich.")
            if n/p > 10000000 and n/p < 100000000:
                print("Es könnte einige Minuten dauern.")
            if n/p > 100000000:
                print("Dauert zu lange - siehe Programm von Sirius")

            a = 3
        
            while a <= n/p:
                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

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

Number.prototype.divides = function(n) { return n % this == 0; };

var primes = function (callback) {
    var primes = [];
    var candidate = 3;
    var testCandidate = function (prime) { return !prime.divides(candidate); };
    var stop = callback(2);
    while (!stop) {
        if (_(primes).every(testCandidate)) {
            primes.push(candidate);
            stop = callback(candidate);
        }
        candidate += 2;
    }
};

var factor = function (n) {
    var result = [];
    primes(function (prime) {
        if (prime.divides(n)) {
            result.push(prime);
            while (n > 1 && prime.divides(n)) n /= prime;
        }
        return n == 1;
    });
    return result;
};

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

main();

Code: Alles auswählen

#!/usr/bin/env coffee

Number::divides = (n) -> n % this == 0


class PrimeGenerator
    constructor: ->
        @primes = []
        @candidate = 1
        @next = @_firstNext

    candidateIsPrime: ->
        for prime in @primes
            if prime.divides(@candidate)
                return false
        true

    _next: ->
        loop
            @candidate += 2
            if @candidateIsPrime()
                @primes.push(@candidate)
                return @candidate

    _firstNext: ->
        @next = @_next
        2


factor = (n) ->
    result = []
    primes = new PrimeGenerator()
    while n > 1
        prime = primes.next()
        if prime.divides(n)
            result.push(prime)
            n /= prime while n > 1 and prime.divides(n)
    result


console.log(factor(parseInt(process.argv[2])))

Code: Alles auswählen

#!/usr/bin/env python
import sys


def iter_primes():
    primes = []
    candidate = 3
    yield 2
    while True:
        if all(candidate % prime != 0 for prime in primes):
            primes.append(candidate)
            yield candidate
        candidate += 2


def iter_factors(number):
    for prime in iter_primes():
        if number == 1:
            return
        if number % prime == 0:
            yield prime
            while number > 1 and number % prime == 0:
                number //= prime


def main():
    if len(sys.argv) < 1:
        print 'usage: {0} number'.format(sys.argv[0])
    else:
        try:
            number = int(sys.argv[1])
        except ValueError:
            print 'Not a valid number:', sys.argv[1]
        else:
            print list(iter_factors(number))


if __name__ == '__main__':
    main()