Fazer uma função FATORES que:
Decompõe o número n em fatores primos e armazena-os nas posições do vetor. O conteúdo de x deve receber o número de fatores primos encontrados. Caso o número de fatores encontrados seja maior que 10, a função deve retornar 1, do contrário deve retornar 0 .
Decompõe o número n em fatores primos e armazena-os nas posições do vetor. O conteúdo de x deve receber o número de fatores primos encontrados. Caso o número de fatores encontrados seja maior que 10, a função deve retornar 1, do contrário deve retornar 0 .
Passo 1
Beleza, então a gente precisa criar uma função chamada FATORES que receba um inteiro n e um vetor v. Essa função vai “quebrar” o n em seus fatores primos, colocando cada fator no vetor v. Também vai atualizar uma variável x com a quantidade total de fatores encontrados. Por fim, se x passar de 10 a função retorna 1, senão retorna 0.
Conteúdo: fatoração em números primos, laços de repetição e condição. Vamos precisar entender como extrair fatores primos (dividindo sucessivamente por números que são primos) e contar quantos saíram.
Conteúdo: fatoração em números primos, laços de repetição e condição. Vamos precisar entender como extrair fatores primos (dividindo sucessivamente por números que são primos) e contar quantos saíram.
Passo 2
Primeiro, o que é fatoração em primos?
Um número inteiro n > 1 pode ser escrito como produto de primos:
n = p₁ · p₂ · … · p_k,
onde cada pᵢ é primo. A ideia é ir testando divisores i começando em 2, enquanto n > 1. Se i divide n (n mod i = 0), então i é um fator primo, a gente guarda i no vetor, faz n := n / i e incrementa x. Se não divide, a gente testa o próximo i. Isso continua até n chegar em 1.
Truque de eficiência: podemos parar a busca quando i² > n, porque se nenhum d ≤ √n divide n, então o n que sobra é primo.
Um número inteiro n > 1 pode ser escrito como produto de primos:
n = p₁ · p₂ · … · p_k,
onde cada pᵢ é primo. A ideia é ir testando divisores i começando em 2, enquanto n > 1. Se i divide n (n mod i = 0), então i é um fator primo, a gente guarda i no vetor, faz n := n / i e incrementa x. Se não divide, a gente testa o próximo i. Isso continua até n chegar em 1.
Truque de eficiência: podemos parar a busca quando i² > n, porque se nenhum d ≤ √n divide n, então o n que sobra é primo.
Passo 3
Pseudocódigo comentado em estilo Pascal:
function FATORES(n: integer; var v: array of integer; var x: integer): integer;
var
i: integer;
begin
x := 0; { zera contador de fatores }
i := 2; { primeiro primo a testar }
while (n > 1) and (i * i <= n) do
begin
if n mod i = 0 then
begin
v[x] := i; { guarda fator primo }
x := x + 1; { conta fator }
if x > 10 then { se passou de 10, já retorna 1 }
begin
FATORES := 1;
exit;
end;
n := n div i; { reduz n }
end
else
i := i + 1; { testa próximo possível divisor }
end;
{ Se sobrou um n > 1, ele próprio é primo }
if n > 1 then
begin
v[x] := n;
x := x + 1;
if x > 10 then
begin
FATORES := 1;
exit;
end;
end;
{ Se não excedeu 10 fatores, retorna 0 }
FATORES := 0;
end;
Resposta
A função FATORES acima decompõe n em primos, armazena em v, conta em x e retorna 1 se x>10 ou 0 caso contrário.