Esercizio 3

[imported_ShuraBozz]

I fattori primi di 13195 sono 5, 7, 13 e 29.

Qual è il più grande fattore prime del numero 600851475143 ?

Soluzione in C:
http://shurabozz.pastebin.com/f6a39f1d9
Qualche warning ma niente di che...

 

[_Wizard]

Il tuo prog mostra tutti i fattori, l'esercizio chiede il più grande ma sono dettagli
Python:

#!/usr/bin/python
def is_prime(n):
	if n == 2:
		return 1;
	if n % 2 == 0:
		return 0;
	p,i = 1,3;
	while i < n:
		if n % i == 0:
			p = 0;
			break;
		i += 2;
	return p;
def Factors(n):
	i = 2;
	l = [];
	while n != 1:
		if n % i == 0 and is_prime(i):
			l.append(i);
			n /= i;
			i = 2;
		else:
			i+=1;
	return l;
print max(Factors(600851475143));

 

[R4z0r_Cr4sH]

[ot]azz questo esercizio in java è complesso...utilizzare numeri a 12 cifre non è semplice![/ot]

 

[_Wizard]

Python coi ; ?!? Ommioddio!
E comunque il fattore primo massimo non è quello che si ottiene dalla scomposizione in fattori primi? Perché il tuo mi sa che stampa il massimo numero primo che lo divide e non il più grande della scomposizione...

I ; li metto per bellezza, lo so che si possono non mettere
Poi i fattori primi sono quei numeri primi che moltiplicati tra loro danno il numero di partenza.

12 | 2
6 | 2
3 | 3
1
12 = 2^2 * 3

I fattori primi di 12 sono 2,2,3. Il maggiore è tre.
Allo stesso modo il mio programma stampa il maggiore fattore primo del numero, come richiesto

 

[imported_opocaj]

EDIT: ho visto che l'esercizio non era come lo intendevo io, quindi source corretto:
[Ruby]

#!/usr/bin/ruby
def isPrime(num)
  (2 .. (num/2).to_i).each do |i|
    return false if num%i==0
  end
  return true
end
$num=600851475143
$prime=1
for i in 3 .. 300425737571 
  if isPrime(i)
    break if $num==1
    if $num%i==0
      $num/=i
      $prime=i
    end
  end
end
puts $prime

 

[jokky]

ed eccolo in c++:

#include <iostream>
using namespace std;

int main()
{
	__int64 num = 600851475143, i = 2;
	while (num > 1)
	{
		if ((num % i) == 0)
		{
			num = num / i;
		}
		else i++;
	}
	cout<<i<<endl;
	cin.get();
	return 0;
}

 

[Mindflyer]

Aggiungo anche il mio codice in python:
EDIT: ho visto che il codice non funzionava, l'ho riscritto

#!/usr/bin/python

# Project Euler Problem 3
# Author = Mindflyer

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

import math

N1 = 600851475143
Primes = []
Factors = []
z = 0

def isprime(n):    #check if integer n is a prime
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True
	

for i in range(1, math.sqrt(N1)):
	if isprime(i):
		Primes.append(i)
		
for x in Primes:
    if N1 % x == 0:
		while z != 1:
			N1 / x == z
			z = x
			Factors.append(x)
			break;			
	
print max(Factors)