Thread: Project Euler 3

Hello, I am really confused on this problem on projecteuler. Its so annoying!!! And its only problem 3! Im using C++ and I am really confused on how to find a technique to find whether a number is prime. My method at the moment is increasing the number that the number I am dividing it by. (600851475143). This method isnt working because I cant really test to see whether a number has more than one decimal point. (Like when 600851475143 / 3. I can use a floating point number because it cannot fit a number that big. Also rounding in C++ isnt that accurate.) Heres an example of some code that I use.

for (int i=0; i <99999; i++);
//code to divide number

Sorry if this isnt that clear... I just need some hints to push me in the right direction.

Thanks!

Originally Posted by Hazique35

Hello, I am really confused on this problem on projecteuler. Its so annoying!!! And its only problem 3! Im using C++ and I am really confused on how to find a technique to find whether a number is prime. My method at the moment is increasing the number that the number I am dividing it by. (600851475143). This method isnt working because I cant really test to see whether a number has more than one decimal point. (Like when 600851475143 / 3. I can use a floating point number because it cannot fit a number that big. Also rounding in C++ isnt that accurate.) Heres an example of some code that I use.

for (int i=0; i <99999; i++);
//code to divide number

Sorry if this isnt that clear... I just need some hints to push me in the right direction.

Thanks!

Use double (the default floating type for most compilers). That will allow 14 digits of integer arithmetic.

.

hmmm... Ive tried that. (probably made a mistake). Ill try it again though.

Thanks!

I'm trying double and it is big enough to hold the number, but Im still having trouble creating the for loop.

Post your code if you're still stuck.

Originally Posted by Hazique35

Hello, I am really confused on this problem on projecteuler. Its so annoying!!! And its only problem 3! Im using C++ and I am really confused on how to find a technique to find whether a number is prime. My method at the moment is increasing the number that the number I am dividing it by. (600851475143). This method isnt working because I cant really test to see whether a number has more than one decimal point. (Like when 600851475143 / 3. I can use a floating point number because it cannot fit a number that big. Also rounding in C++ isnt that accurate.) Heres an example of some code that I use.

for (int i=0; i <99999; i++);
//code to divide number

Sorry if this isnt that clear... I just need some hints to push me in the right direction.

Thanks!

I have a feeling that your way of checking primes might be inefficient. Perhaps not, but you never know. I've attached my code.

Use unsigned long longs for the big numbers. Your number returns 0, i.e. false. It's not a prime.

Code:

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

bool isPrime(unsigned long long n)
{
    unsigned long long root = floor(sqrt(n)) + 1;

    for (unsigned long long i = 2; i <= root; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    bool Prime = isPrime(600851475143ULL);
    cout << Prime << endl;
    return 0;
}