C++

Forum

 
trying to reduce the overhead on my program that is supposed to find the highest prime of 600851475143

Pages: 12
devonrevenge (2435)
I have reduced it for lower numbers but for some reason with higher numbers when i get the program to out put all the primes they are in minuses!!!

i need a way to make this even faster, or maybe theres a better mathematical answer, I know that for numbers in their 1,000,000,000,000 have an average of 1 prime every 26.6 numbers (i think thats right there is 37,607,912,018 primes in the number 1,000,000,000,000) is there anyway i can utilize this??


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <iostream>

using namespace std;

int main()
{
    int primeanswer = 1,p = 1;
    for (int i=1;i<35; i++)
    {
        int factorcount = 0;
        for(int p = 1; p<i; p++)
        {

            if((i%p)==0)
            {
                factorcount++;

            }
        }

        if(factorcount<=1)
        {
            //cout<<i<<"\n";
            primeanswer = i;

        }
    }
    cout<<primeanswer;
}


EDIT:put wrong program in, this is the one!
Last edited on
naraku9333 (2163)
Those numbers are too big for an int, try unsigned long long. And your code seems to be looking for factors, not primes.
devonrevenge (2435)
yeah i put the wrong one in earlier, thanks i will try
devonrevenge (2435)
okay heres version with longs, still has to do a lot of work though

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <iostream>

using namespace std;

int main()
{
    long primeanswer = 1,p = 1;
    for (long i=600851470000;i<600851475143 ; i++)
    {
        int factorcount = 0;
        for(long p=1; p<i; p++ )
        {

            if((i%p)==0)
            {
                factorcount++;
                   
                      //adding this helped
                 if(factorcount>=2)
                    {
                       break;
                    }

            }

        }

        if(factorcount<=1)
        {
            primeanswer = i;
        }
    }
    cout<<primeanswer;
}
Last edited on
naraku9333 (2163)
Long is still not big enough, try unsigned long long.
Edit: you also won't find any factors using that as a starting number.
Last edited on
devonrevenge (2435)
OMG I CAN COUNT DOWN!! :P

still slow :'(

any other hints??
Last edited on
devonrevenge (2435)
theres got to be a better way of doing this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
int main()
{
    long long primeanswer = 1,p = 1;
    for (long long i=600851475143 ;i>0; i--)
    {
        int factorcount = 0;
        for(long long p=1; p<i; p++ )
        {

            if((i%p)==0)
            {
                factorcount++;
                if(factorcount>=2)
                    {
                       break;
                    }
            }

        }

        if(factorcount<=1)
        {
            primeanswer = i;
            cout<<primeanswer<<" ";
        }
    }

}
cire (8284)
any other hints??

Factors occur in pairs.
Smac89 (1727)
Very basic form of prime finding. Other methods include primesieve which is quite fast for large numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <inttypes.h>
#include <deque>
#include <map>
#define INIT(a,b) memset(a, b, sizeof(a))
#define even(_) ((_^2 && ~_&1))
#define all(G) G.begin(), G.end()
#define MAX 1000000
#define pii pair<int, int>
#define cond(P, E) P = E.begin(); P != E.end(); ++P

using namespace std;

bool isPrime( long long the_Num ) {
	long G = sqrt(the_Num);
	for ( int t = 3; t <= G; t += 2 ) {
		if ( the_Num % t == 0 )
			return false;
	}
	return true;
}

int main() {
	for (long long i = 600851475143 ;i > 1; --i ) {
		if ( !even(i) && isPrime(i) )
			cout << i << " ";
	}
	cout << "\n";
}
Last edited on
devonrevenge (2435)
oh yeh and prime numbers are not even either :P
Smac89 (1727)
Yup, so you can even do i-=2 instead of --i
cire (8284)
Counting down won't make any appreciable difference. The largest prime factor is considerably smaller than the number.

Factors come in pairs. For at least one solution to this problem, testing for primality is not necessary.

  100
  /\
(2  50) - pair
    /\
  (2  25) - pair
      /\
    (5  5) - pair


Last edited on
devonrevenge (2435)
it is indeed faster now that square roots are modulized, but still too slow :/
devonrevenge (2435)
this is what i came up with, i wonder how many years untill it outputs the result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 long long primeanswer = 1,p = 1,sqrt_of_i;
    int factorcount = 0;
    for (long long i=600851475143;i>0; i=i-2)
    {
        factorcount =0;
        for(long long p=1; p<i; p++ )
        {
             sqrt_of_i = sqrt(i);
            if((i%p)==0)
            {
                factorcount++;
                if(factorcount>=2)
                    {
                        break;
                    }
            }

        }

        if(factorcount<=1)
        {
            primeanswer = i;
               cout<<primeanswer<<" ";
        }
    }
Smac89 (1727)
Your algorithm's worst case is still O(n^2) when it should be O(nsqrt(n))

You should be doing something with that sqrt you calculated. Look at the code I posted
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <cstdint>
#include <iostream>
#include <cmath>
#include <vector>

bool prime( std::uintmax_t number, const std::vector<bool>& sieve )
{
    const std::size_t SZ = std::ceil( std::sqrt(number) ) + 1 ;
    for( std::size_t i = 2 ; i < SZ ; ++i )
        if( sieve[i] && !(number%i) ) return false ;
    return true ;
}

int main()
{
    std::uintmax_t N ;
    if( std::cout << "N? " && std::cin >> N )  // 600851475143 ;
    {
        const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ;

        // generate a prime number sieve upto the square root of N
        std::vector<bool> sieve( SZ, true ) ;
        for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] )
              for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ;

        std::uintmax_t largest_prime_factor = 1 ;

        // start with 1 because N may be a prime
        for( std::size_t i = 1 ; i < SZ ; ++i ) if( sieve[i] && N%i == 0 )
        {
            if( prime( N/i, sieve ) )
            {
               largest_prime_factor = N/i ;
               break ; // N == x*i, x>sqrt(N), and x is a prime
            }
            else largest_prime_factor = i ;
        }

        std::cout << "largest prime factor of " << N << " is "
                   << largest_prime_factor << '\n' ;
    }
}

http://ideone.com/DG2zY9

Note: This solution is broken http://www.cplusplus.com/forum/beginner/89932/#msg483285

As shown by tntxtnt: http://www.cplusplus.com/forum/beginner/89932/#msg483503
I'd missed the post at that time; so a belated thank you!
Last edited on
devonrevenge (2435)
oh yeh i think i lost concentration about there, I thought i had done something with square root
devonrevenge (2435)
Interesting, the project euler problem is the largest prime factor of that number, i was finding the next nearest prime number to that number, however, i would like to continue my original challenge, but i suspect that it will still take a long time to find the nearest prime number but will be quite easy to find the highest prime factor what with all the doubling increasing of P
Last edited on
devonrevenge (2435)
BOOM OMG THATS SO QUICK!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
int main()
{
    //initialize some long ass integers
    long long primeanswer = 1,p = 1,sqrt_of_i;
    //flag for counting a discovery of a factor
    int factorcount = 0;
    //for loop counts down in twos from an odd number i is number to check
    for (long long i=600851475145;i>0; i=i-2)
    {
        //reset factor count flag to zero
        factorcount =0;
        //squaring i means that finding a factor of i wont take as long
        sqrt_of_i = sqrt(i);
        //loop usues p to get numbers fo checking against square of i
        for(long long p=1; p<=sqrt_of_i; p++ )
        {
            //if there is a remainder of 0 when diveded...
            if((i%p)==0)
            {
                //then a factor has been found, the integer is incremented
                factorcount++;
                //if there is more than two factors the we are not dealing with a prime
                if(factorcount>=2)
                    {
                        break;
                    }
            }

        }
        //if we found only one factor (1) then we output the prime :D
        if(factorcount<=1)
        {
            primeanswer = i;
               cout<<primeanswer<<" ";
        }
    }

}


took me a while, i never knew that squaring i would make it that much faster
Last edited on
JLBorges (13770)
> BOOM OMG THATS SO QUICK!!

And also so wrong.

Try running the program, first for finding the largest prime factor of 74
1
2
 
//for (long long i=600851475145;i>0; i=i-2)
for (long long i=74;i>0; i=i-2)


And then for finding the largest prime factor of 161
for (long long i=161;i>0; i=i-2)
Pages: 12