Ir ao conteúdo
  • Cadastre-se
alecounter

C++ Implementar função em C++

Recommended Posts

Pessoal, tudo bem? alguém poderia por gentileza me indicar o erro deste algoritmo que verifica se o número é primo ou não? O erro é que a função só retorna true!

 

bool primo(int n) {
    for(int i = 2; i < int(sqrt(n)); i++)
        if(n % i == 0) return false;
    return true;
}

int main() {
    std::cout << primo(5);
}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

O que acontece é que,  raiz-2 de 5 é menor que 3 e maior que 2: porém o valor 2 é retornado pelo casting~int;

Não satisfazendo a condição de i  <  2, pois i = 2.

Compartilhar este post


Link para o post
Compartilhar em outros sites
agora, AnsiC disse:

O que acontece é que,  raiz-2 de 5 é menor que 3 e maior que 2: porém o valor 2 é retornado pelo casting~int;

Não satisfazendo a condição de i  <  2, pois i = 2.

eu coloquei outra condição, fiz assim

 

for(int i = 2; i < n; i++)

e mesmo assim a coisa ainda não funciona!

Compartilhar este post


Link para o post
Compartilhar em outros sites
9 minutos atrás, alecounter disse:

e mesmo assim a coisa ainda não funciona!

Só não funciona para 2, para os demais números naturais funciona.

 

Compartilhar este post


Link para o post
Compartilhar em outros sites
10 minutos atrás, AnsiC disse:

Só não funciona para 2, para os demais números naturais funciona.

 

por qual motivo isto está acontecendo?

Compartilhar este post


Link para o post
Compartilhar em outros sites
Em 28/07/2018 às 13:36, alecounter disse:

eu coloquei outra condição, fiz assim

 


for(int i = 2; i < n; i++)

e mesmo assim a coisa ainda não funciona!

Estude o que é um número primo, mais seu algoritmo básico de primalidade: https://pt.wikipedia.org/wiki/Número_primo

 

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Eu já sei a definição de número primo. O que isso tem a ver com o problema?

adicionado 9 minutos depois

Problema resolvido. Uma pequena alteração no código resolveu o problema :D estranho que na faculdade eu fiz a mesma coisa e não funcionou por lá... Lá na faculdade é Linux e aqui windows, será que tem algo a ver?

adicionado 17 minutos depois
3 horas atrás, AnsiC disse:

Só não funciona para 2, para os demais números naturais funciona.

 

se o meu número n for da forma n=2k, pra k natural, então deveria funcionar para o 2 também. o código não funcionou por algum motivo desconhecido, já que copiei e colei aqui no codeblocks em casa e tudo funcionou bem...

Compartilhar este post


Link para o post
Compartilhar em outros sites
Visitante

@alecounter Aqui tem uma outra forma p usar em sua função p verificar se um número é primo:

#include <iostream>
using namespace std;

bool ehPrimo(int n) {

    int div = 0;

    for (int i = 1; i <= n; i++)
        if (n % i == 0) div++;

    return ((div == 2) && (n > 1));
}

int main() {

    for (int i = 0; i < 100; i++)
        if (ehPrimo(i))
            cout << i << " ";

    cout << endl;

    return 0;
}

Vê se entende a lógica usada, ok?

  • Curtir 1
  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
1 hora atrás, alecounter disse:

Eu já sei a definição de número primo. O que isso tem a ver com o problema

Tem tudo, @giu_d já demonstrou o quanto saber, e não pensar que sabe, é importante.

adicionado 5 minutos depois
1 hora atrás, alecounter disse:

código não funcionou por algum motivo desconhecido, já que copiei e colei aqui no codeblocks em casa e tudo funcionou bem..

Talvez porque 2 é o único primo par. Portanto 2%2 = 0 e ainda sim 2 é primo. Coisa que você só diz saber, e que explica o porquê de não funcionar exclusivamente com 2. 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
21 horas atrás, AnsiC disse:

Tem tudo, @giu_d já demonstrou o quanto saber, e não pensar que sabe, é importante.

adicionado 5 minutos depois

Talvez porque 2 é o único primo par. Portanto 2%2 = 0 e ainda sim 2 é primo. Coisa que você só diz saber, e que explica o porquê de não funcionar exclusivamente com 2. 

não amigo, eu simplesmente copiei o código que estava aqui no post no meu codeblock para windows e tudo funcionou bem. precisei apenas fazer uma alteração aqui:

for(int i = 2; i <= int(sqrt(n)); i++)

pois realmente não sabia que o valor de sqrt(n) seria truncado, pensei que fosse arredondado. Não sei o motivo pelo qual não funcionou no ambiente Linux onde estava anteriormente. Basicamente eu nem segui nada do que vcs disseram aqui

adicionado 2 minutos depois
21 horas atrás, giu_d disse:

 

Vê se entende a lógica usada, ok?

entendi a lógica sim, obrigado pelo algoritmo

como já disse, fiz uma alteração no código que fiz anteriormente e tudo funcionou bem

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Então 0, 1 também são primos, pois ambos são naturais e menores que 2.

Compartilhar este post


Link para o post
Compartilhar em outros sites
1 minuto atrás, AnsiC disse:

Então 0, 1 também são primos, pois ambos são naturais e menores que 2.

aí é só tratar exceções... só colocar um if-else que leva alguns nanossegundos para ser computado

Compartilhar este post


Link para o post
Compartilhar em outros sites
Em 28/07/2018 às 20:17, alecounter disse:

aí é só tratar exceções... só colocar um if-else que leva alguns nanossegundos para ser computado

Pois é, dependendo da máquina ambos os algoritmos têm o mesmo desempenho a com diferenças lógicas; é que o seu não trata as exceções , ou não tratava tratadas.

 

Beleza se acha que deve, post seu versão otimizada.

 

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

não vejo outra alternativa a não ser usar exceções, em especial pelo caso n=0.

pelo algoritmo de euclides, se um número 'a' natural divide 0, então o quociente também é 0 e podemos escrever

0=0a. Percebe-se assim que qualquer valor contido no conjunto dos inteiros satisfaz isso, logo fica indeterminado. Contar divisores nesse caso não funciona(mesmo).

adicionado 2 minutos depois

algoritmo da divisão ***

Compartilhar este post


Link para o post
Compartilhar em outros sites
19 horas atrás, AnsiC disse:

pois é, dependendo da máquina ambos os algoritmos têm o mesmo desempenho. A diferença é que o seu não trata as exceções, ou não tratava. Beleza se acha que deve post seu versão otimizada.

a complexidade computacional dos algoritmos não é igual. no meu algoritmo, a decisão de o número 'n' ser um primo ou não se baseia no fato de algum número contido em {2,3,...,int(sqrt(n))} dividir n. Se isso acontecer, a função cospe a resposta imediatamente.

No caso do algoritmo do colega acima, o laço percorre o conjunto {1,2,...,n-1} em todos os casos e ainda itera sobre uma variável toda vez que ocorre uma divisão inteira. Podemos observar também que valores acima de int(sqrt(n)) nem precisariam ser verificados, pelo teorema fundamental da aritmética...

 
  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Completando para sirva de referência: No artigo do atalho no post#6 em que há uma perfeita definição de número primo e outras hiperligações. Entre descrito o algoritmo básico de primalidade: divisões sucessivas ou Crivo de Eratóstenes, para todos entenderem.

 

Assim eu entendo que:

Na sua forma mais ingenua: para se determinar um número primo (ou primalidade de um número inteiro) qualquer basta apenas testar se o inteiro natural é:

  1. COMPOSTO: Um número composto, é o oposto ao número primo, é número fatorável: é divisível exato e por fatores primos.

 

O livro tudo em matemática 7 de matemática 0 (ou básica) ensina muito bem como fazer isso, em resumo:

  • Basta verificar se o número tem raiz exata;
  • Ou se é divisível por 2;
  • Testar para todos valores ímpares de 3 até raiz-2 do número: é divisível exato- se sim: Daí não será primo.
  • Nem todo número natural menor que 4 é primo: 0, e 1 não é primo.

 

 

Implementar função em C++

Spoiler

#include <cmath>
/*
 * primalidade de numero natural */
char esprimo (int numero){
  float raiz_numero;
  char sim = 1, nao = 0;
    if (numero < 2){return nao;} else
    if (numero < 4){return sim;} else
    if (numero%2 == 0){return nao;} else
    if (int (raiz_numero = sqrt (numero)) == raiz_numero){return nao;} else
    for (int k = 3; k < raiz_numero; k += 2){if (numero%k == 0){return nao;}}
  return sim;};

 

 

 

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Muito simples, ingênua e bem implementada gostosa de se olhar!

Dúvidas?

Compartilhar este post


Link para o post
Compartilhar em outros sites
2 horas atrás, AnsiC disse:

ingênua

O que você quer dizer com ingênua? Inocente ou simples? E qual seria a versão não ingênua?

  • Haha 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×