Trying to find highest prime number but i cant get it working corectly

[Oriphin]

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;
//---------------------------------------------------------------------------//
// Function: |isPrime| takes an int and returns a bool of 0 if the number is //
// not Prime and a value of 1 if number is prime                             //

bool isPrime ( int a ){
    for (int i = ( a - 1); i > 1; i--){
        if ((a%i)==0)
            return (false);
        }
        //when all renainders are =/= o, a = prime number
        return(true);
}
//------------------------end of isPrime-------------------------------------//
//---------------------------------------------------------------------------//
//Function: |largest_prime_factor| will take a integer and return the largest//
// prime number that it is divisable by first checking if the number is      //
//divisable by the number if it is then it will check for prime and if it is //
//prime it will return it and break the function as this will be the highest //
int largest_prime_factor(int a){
    for(int i = (a); i > 0; i--){
            if ((a%i)==0){     //number is devidable by i
               bool Prime = 0;
               cout <<"Prime before isPrime is: " << Prime << endl;
               Prime = isPrime(i);
               cout << "Prime after isPrime is: " << Prime << endl;
               if (Prime = 1){
                  cout << "in if statemnet i = " << i << endl;
                  return i;
                  break;
               }
            }
    }
}

this are my two functions that i have made and it should return the highest prime number that it is deviable by but unfotianately it dosnt it returns the highest number it is devisable by prime or not prime

i cant see where im going wrong so ny sugetions would be great

thankyou

EDIT: i know that the isPrime function wors 100%

EDIT 2 : updated a bit

[laserlight]

Trying to find highest prime number

Good luck, hope you are immortal

it should return the highest prime number that it is deviable by

You mean "perfectly divisible", not "deviable", right? And by what?

[Oriphin]

woops sorry i ment the highest prime number that a number is divisable by sorry for my bad spelling

eg

n = 14
largest_prime_number = 7

[DragForce]

isPrime function works but it is written in, probably, the most inefficient way. Try using something like that

 
bool isPrime ( int a ){
	if (a < 2)
	  return false;
 
	int sqrt_a = static_cast<int>(sqrt(a));
 
	if (a%2 == 0)
	   return (a == 2) ? true : false;

	for (int i = 3; i <= sqrt_a; i+=2){
		if ((a%i)==0)
			return (false);
		}
		//when all renainders are =/= o, a = prime number
		return(true);
}

[Oriphin]

solved it sorry guys i was useing = instead of == **** what was i thinking lol

[Oriphin]

can you tell me what is inefficient about isPrime, sorry still learning so i want to know as much as i can about optimising

thankyou

[RoboTact]

You try to divide by all values less then a, DragForce's method only by least sqrt(a) values. It's in sqrt(a) times less.

[DragForce]

Let N be the value of you parameter. So the size of input is M= log N - the length of input (its binary representation).

Yours version makes ~N divisions and comparisons, which is equivalent to O(2^M) operations.

In my version ~SQRT(N)/2 divisions and comparisons are done, which is equivalent to O(2^SQRT(M)) operations.

Now assume, that paramter "a" has value 2^30. Your algorithm will check it in ~2^30 time units, while mine will do that in ~2^14 time units, which is clearly better.

Clearly there are more effective implementations than mine, but they are more difficult to code.

[SuperKoko]

You can get a much greater efficiency, by computing all prime divisors of the number (decompose the number in prime factors).
Then, simply search the max number in this prime factors list.

[Oriphin]

Let N be the value of you parameter. So the size of input is M= log N - the length of input (its binary representation).

Yours version makes ~N divisions and comparisons, which is equivalent to O(2^M) operations.

In my version ~SQRT(N)/2 divisions and comparisons are done, which is equivalent to O(2^SQRT(M)) operations.

Now assume, that paramter "a" has value 2^30. Your algorithm will check it in ~2^30 time units, while mine will do that in ~2^14 time units, which is clearly better.

Clearly there are more effective implementations than mine, but they are more difficult to code.

yes i can see the greatger efficiancy of that but one problem i cant use other librarys and isnt sqrt() part of cmath?
But yes 2^30 is much larger than 2^14

[Oriphin]

You can get a much greater efficiency, by computing all prime divisors of the number (decompose the number in prime factors).
Then, simply search the max number in this prime factors list.

what do you mean by "decompose the number in prime factors"

thankyou

[DragForce]

You can get a much greater efficiency, by computing all prime divisors of the number (decompose the number in prime factors).
Then, simply search the max number in this prime factors list.

I am not sure that full decomposition is as fast as this check:

 
int get_lagest_blah_blah( int a ){

for (int i = a%2; i > 1; --i)
{
		if (((a%i)==0) && (isPrime(i)))
	return i;
 }
return 1; // a is prime itself
}

[SuperKoko]

I am not sure that full decomposition is as fast as this check:

for (int i = a%2; i > 1; --i)

Hummm...
Yes, you routine is really very very fast, since a%2<=1, and thus the loop is never entered, and your function always returns 1.

However, my routine works as expected!
But, the OP method is really extremely slow (complexity is O(N)) : Think at that : In the best case, the number is equal to the double of a prime number, and there will be N/2 loops, followed by a isPrime test!

My function will have a complexity equal to O(sqrt(N)) in the worst case (the same complexity than a simple call to isPrime)!

[DragForce]

for (int i = a%2; i > 1; --i)

Hummm...
Yes, you routine is really very very fast, since a%2<=1, and thus the loop is never entered, and your function always returns 1.

Sorry about that typo. I really meant using "/" rather than "%".

But, the OP method is really extremely slow (complexity is O(N))

I am afraid to say but you misunderstand the notion of computational complexity.

Computational complexity is calculated with respect to the size of the input data. If function takes a number N, then the size of the input is O(log_2(N)), unless it is represented in an unusual way, e.g. unary form, when it is O(N).

That is why if one enumerates all numbers from 1 to N, then the complexity is not linear but exponential. (Well, some data encryption algorithms use the fact that finding devisors of a number is exponentially complex)

In my algorithm isPrime is called only if our number is divisible by i and certainly it is not true for every i in general case.

It is clear that the speed of this routine can be easily improved if some tests that number "a" can be devided by 2, 3, 5, 7, 11, ..., p, are moved in front of the loop. Then we can start with i=a/p rather than with i=a/2.

Moreover, if one really cares about performance of this function then a table of prime numbers has to be precomputed and "i" in the loop should traverse elements of that table rather than all integers.

[SuperKoko]

Sorry about that typo. I really meant using "/" rather than "%".


I am afraid to say but you misunderstand the notion of computational complexity.

Computational complexity is calculated with respect to the size of the input data. If function takes a number N, then the size of the input is O(log_2(N)), unless it is represented in an unusual way, e.g. unary form, when it is O(N).

That is why if one enumerates all numbers from 1 to N, then the complexity is not linear but exponential. (Well, some data encryption algorithms use the fact that finding devisors of a number is exponentially complex)

In my algorithm isPrime is called only if our number is divisible by i and certainly it is not true for every i in general case.

It is clear that the speed of this routine can be easily improved if some tests that number "a" can be devided by 2, 3, 5, 7, 11, ..., p, are moved in front of the loop. Then we can start with i=a/p rather than with i=a/2.

Moreover, if one really cares about performance of this function then a table of prime numbers has to be precomputed and "i" in the loop should traverse elements of that table rather than all integers.

No, I know well algorithmic complexity, but I was refering to your notation:

Let N be the value of you parameter. So the size of input is M= log N - the length of input (its binary representation).

For matter of simplification, I wrote complexities in tem of N, but I could also use the more conventional M.

In my algorithm isPrime is called only if our number is divisible by i and certainly it is not true for every i in general case.

My algorithm as the same complexity that this naive implementation of isPrime.
But, with a naive implementation, I am almost sure that my algorithm will be faster.

For example, with your algorithm applied to numbers divisible by 3 the loop will be executed at least (N/2-N/3)==N/6 times.
Thus, complexity is O(N) in that case (or O(exp(M)) if you prefer).
While the complexity of my algorithm is O(sqrt(N)).