when I put a small number in my algorithm it works, but if the number is large the program returns 0

Asked

Viewed 64 times

0

when I put a small number in my algorithm it works, but if the number is large the program returns 0, I tried to put unsigned int, long, etc and it didn’t work... Here’s the code:

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

/*
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/

int primo(int num);//declarando a função
int menorDiv();
const long numz = 600851475143;

int main(){

    //1 - pegar os divisores do numero
    //2 - verificar se esse divisor é primo
    //3 - pegar o maior divisor primo do numero 600851475143

    int i, maior = 0, primao;
    for ( i = 1; i <= menorDiv(); i++){
        if( i % 2 == 0)
            continue;
        if ( primo(i)  == 0){//se for primo
            if ( numz % i == 0){
                primao = i;
            }
        }
    }

    printf("%d", primao);
    return 0;
}

int menorDiv(){//pega o menor divisor do numero grandao
    int i, menor;
    for ( i = 1; i < numz; i++){
        if( numz % i == 0){
            menor =  (float)numz/i;
            break;
        }
    }
    return menor;
}

int primo(int num){
    int i, contador = 0;

    for ( i = 1; i <= num; i++){
        if( num % i == 0){
            contador++;
        }
    }
    if ( contador == 2){
        return 0;
    }
    return 1;
}

I made some edits in the code and the final version was like this:

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

/*
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/
const long long num = 600851475143;
long long menorDiv(long long num);
long long primo(long long i);

int main(){

    // 1 - pegar os divisores primos
    // 2 - pegar o maior

    long long i, primu;//declara i como long long
    for ( i = 0; i < menorDiv(num); i++){
        if ( primo(i) == 0){//caso seja primo faça
            if( num % i == 0){
                primu = i;
            }
        }
    }

    printf("%ld", primu);
    return 0;
}
long long menorDiv(long long num){//pega o menor numero que seja divisivel pelo numero para que o programa nao continue rodando apos esse numero
    long long i, result;
    for ( i = 1; i <= num; i++){
        if( num % i == 0){
            result = num/i;
            break;
        }
    }
    return result;
}
long long primo(long long i){
    int contador = 0;
    long long j;
    for ( j = 1; j < i; j++){
        if( i % j == 0){
            contador++;
        }
    }
    if( contador == 2){
        return 0;
    }
    return 1;
}

But still unsuccessful, the code keeps running and not stopping... it seems to have gone into infinite looping, but I can’t find anywhere that this might have happened

  • when I put 13195 on numz the result of 29 that is correct, but when putting 600851475143 returns 0, it should return 6857

3 answers

2

You stated:

const long numz = 600851475143;

and here does:

int i, menor;
for ( i = 1; i < numz; i++){

Note that i is an int and an int does not hold this numz value. Maybe you should use long long for such variables and double for the division.

  • so ?: long long i; double minor;

  • It is also worth mentioning that with printf("%d", minha_var) the value of a long will not be printed correctly, have to use printf("%li", minha_var)

  • Yes. Maybe even make the division with long long operands.

2

You must declare the minor variable and i, as long const

const long menor;
const long i;

for ( i = 1; i < numz; i++){...

Note: You should also change all variables int for const long.

  • 3

    I don’t think it makes much sense to declare there as const if the value of i will vary in the loop.

0

I started to redo the code from scratch and managed to solve the problem, here is the code optimized and functional:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//biblioteca booleana

/*
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/
bool primo(long num);//declarando a funcao
int main(){

    for ( long i = 1; i < 600851475143; i++){
        if ( 600851475143 % i == 0 && primo(600851475143/i)){//caso seja primo e divisivel pelo numero retorna esse valor
            printf("%li", 600851475143/i);
            return 0;    
        }
    }
}

bool primo( long num){//checa se o numero e primo
    long i;
    for ( i = 2; i < num; i++){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

tip for some who are starting out: Sometimes it is better to start over and solve the problem from scratch than to solve a part of the problem and later have to solve again and again and so on! " Nip it in the bud"

Browser other questions tagged

You are not signed in. Login or sign up in order to post.