Algorithm in C - Prime numbers

Question

Algorithm in C - Prime numbers

Navigation

#1 by (2 votes)
#2 by (1 votes)

2

The program has to perform a prime number check, where the user enters a number and the program finds the largest prime number prior to it. the problem with my program is that it does not verify until the end, for example, if I write 10, I should find 7 but he thinks 5 is always 5.

#include <stdio.h>
#include <stdlib.h>

/*.
  .
  .
  7)receber um numero inteiro e falar o maior numero primo que seja o anterior a este*/

int main()
{
    int opc;/*1-switch*/
    int numA=0, numB=0, numC=0, soma, aux=0; /*variaveis para calculos*/
    int i, j;/*contadores*/
    int vet[10];/*vetores inteiros*/
    float media;/*variaveis para calculos*/

    printf("escolha qual exercicio quer executar:\n7)Ex7\n");
    scanf("%i", &opc);

    fflush(stdin);
    system("cls");

    switch(opc)
    {
        /*.
          .
          .
          */
    case 7:

        printf("digite um numero:\t");
        scanf("%i", &numA);

        /*inicio da fase de processamento*/

        numB=1; /*para dar inicio ao calculo de achar numero primos por tentativas*/
        numC=0;
        j=0;/*reset do contador*/
        int cont=0, y, aux2=0;

        if(numA==0 || numA==1 || numA==2)
        {
            printf("%i nao tem numero primo, anterior a ele.", numA);
            break;
        }else
        {
            for(i=0; i<numA; i++)
            {
                aux=cont/2;
                for(y=0; y<aux; y++)
                {
                    numC=cont%numB;/*faz divisao modular da variavel de entrada com     numB=1*/

                    fflush(stdin);

                    if(numC==0)/*verifica se resultado deu 0*/
                        j=j+1;/*se sim armazena em j um marcador +1/+1*/

                    numB=numB+1;/*e soma 1 ao numB para acompanhar o valor de aux*/
                }

                fflush(stdin);

                if(j==1)
                {
                    aux2=cont;
                }

                cont=cont+1;
                j=0;/*reset do contador*/

                printf("\n\n\n[%d]\n\n\n", aux2);/*verificação de variavel*/                
                printf("\n\n\n%d\n\n\n", cont);
            }

            printf("%d eh o maior numero primo antes de %i", aux2, numA);
        }

        /*fim da fase de processamento*/

        break;

    default:
        break;
    }

    return 0;
}

SOLUTION FOUND

/*inicio da fase de processamento*/

    for(i=0; i<numA; i++)
    {
        aux=numA-1;/*subtraio 1 ao numero original*/

        if(comPrimos(aux)==true)/*mando para uma função o valor armazenado na aux para verificar se é primo*/
        {/*se for verdadeiro faça*/
            printf("%d eh o maior numero primo antes de %i", aux, aux2);
            break;/*quebrar para sair do for*/
        }

        numA=aux;
    }

    /*fim da fase de processamento*/

FUNCTION

int comPrimos(int prim)
{
    int i, aux, B, j=0;

    aux=prim/2;

    int A=1;

    for(i=0; i<aux; i++)
    {/*verificação por tentativas de divisão modular*/
        B=prim%A;

        if(B==0)
            j=j+1;

        A=A+1;
    }

    fflush(stdin);
    system("cls");

    if(j==1)
        return true;

    else
        return false;

}

c algoritmo

asked by anonymous 16.04.2015 / 22:48

2 answers

1

Well there goes an example solution to your problem. It is based on generating a vector containing 1 for numbers that are prime and 0 for numbers that are not, is the famous raster of Eratosthenes. In other words, sieve [19] will return 1, because 19 is prime and sieve [25] will return zero, since 25 is not prime.

The sieve is made by starting as if all numbers are prime, hence if you draw all multiples of 2, then all multiples of 3, then 5, and so on until only the prime numbers are left. After mounting the sieve the rest of the program is quite easy to do.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define tamanho_crivo 10000

int main()
{
    int num, i, j, resp=0;

    // Monta o vetor para determinar se um número é primo ou não
    char crivo[tamanho_crivo];
    memset(crivo, 1, tamanho_crivo);
    crivo[0] = 0;
    crivo[1] = 0;
    for(i=2; i < tamanho_crivo; i++){
        if(crivo[i] == 1)
            for(j=2*i; j < tamanho_crivo; j = j+i)
                crivo[j] = 0;  // Números que não são primos, pois são divisíveis por i 
    }

    printf("Digite um numero inteiro positivo:\n");
    scanf("%i", &num);

    for(i=num; i > 1; i--)
        if(crivo[i]){
            resp = i;
            break;
        }

    // Imprime os resultados
    if(resp==0)
        printf("Nao tem numero primo anterior\n");
    else
        printf("%d e o maior numero primo antes de %d\n", resp, num);

    return 0;
}

22.04.2016 / 03:01

How to organize the body of HTML on the screen with CSS Wait for pending executions to finish to proceed, JavaScript

score 2 · Accepted Answer

As it seems to be a didactic problem I will just leave a suggestion, I do not know if it can be valid here in Stak . If not put the code later.

I would start thinking in a different way, imagine that the user enters a very high nmr, the system goes from 0 until it gets close to that number, because instead of starting from 0 the loop does not start from the number that the user entered, then you decremented each interaction, and as soon as you find the first prime number you leave the loop, saving processing and dispensing temporary variables, the for function would be more or less like this

    for(i=numA-1; i>0; --i)
          if(isPrimo(i)){
                printf(" primo anterior %d", i);
                break;
          }