Reputation: 109
So I have the following problem. They give me an array w/ n numbers and I have to print if it contains any prime numbers using "Divide et Impera". I solved the problem but it gets only 70/100 because it isn't efficient(they say).
#include <iostream>
using namespace std;
bool isPrime(int x){
if(x == 2) return false;
for(int i = 2; i <= x/2; ++i)
if(x%i==0) return false;
return true;
}
int existaP(int a[], int li, int ls){
if(li==ls)
if(isPrime(a[li]) == true) return 1;
else return 0;
else return existaP(a, li, (li+ls)/2)+existaP(a, (li+ls)/2+1, ls);
}
int main(){
int n, a[10001];
cin >> n;
for(int i = 1; i<=n; ++i) cin >> a[i];
if(existaP(a,1,n) >= 1) cout << "Y";
else cout << "N";
return 0;
}
Upvotes: 3
Views: 22053
Reputation: 29
bool isprime(int x)
{
if(x <= 1) return false;
if(x == 2 || x == 3) return true;
if(x % 2 == 0 || x % 3 == 0) return false;
if((x - 1) % 6 != 0 && (x + 1) % 6 != 0) return false;
for(int i = 5; i * i <= x; i += 6)
{
if(x % i == 0 || x % (i + 2) == 0) return false;
}
return true;
}
If prime numbers need to be printed for a particular range or to determine whether a number is prime or not, the sieve of the eratosthenes algorithm is probably preferable as it is very efficient in terms of time complexity O( n * log2( log2(n) ) )
, but the space complexity of this algorithm can cause an issue if the numbers are exceeding certain memory limit.
We can optimize this simpler algorithm which has a time complexity of O(n1/2)
by introducing few additional checks based on this thoerem as shown in the above isprime code block
.
Despite the fact that Sieve of Erathosthenes algorithm is efficient in terms of time complexity under space restrictions, the above provided isprime code block
can be utilized, and there are numerous variations of the Sieve of Erathosthenes algorithm that perform considerably better, as explained in this link.
Many more algorithms exist, but in terms of solving coding challenges, this one is simpler and more convenient. You can learn more about them by clicking on the following links:
Upvotes: 2
Reputation: 1
This is a much faster algorithm in my opinion. It works on the Euclidean algorithm to calculate H.C.F. Basically, I check if the HCF of the number AND the consecutively second number is 1; and if the number itself is divisible by either 2 or 3. Don't ask how I mathematically reached the solution, it just struck me :D. The time complexity of this solution is O(log (max(a,b))), which is notably smaller than the time complexity of the program which runs a loop counter 2 to sqrt(n) is O(sqrt(n)).
#include <iostream>
using namespace std;
int hcf(int, int);
int hcf(int a, int b)
{
if (b == 0)
{
return a;
}
return hcf(b, a % b);
}
int main()
{
int a;
cout << "\nEnter a natural number: ";
cin >> a;
if(a<=0)
{
cout << "\nFor conventional reasons we keep the discussion of primes to natural numbers in this program:) (Read: Ring of Integers / Euclid's Lemma)";
return 0;
}
if (a == 1)
{
cout << "\nThe number is neither composite nor prime :D";
return 0;
}
if (a == 2)
{
cout << "\nThe number is the only even Prime :D";
return 0;
}
if (hcf(a, a + 2) == 1)
{
if (a % 2 != 0 && a % 3 != 0)
{
cout << "\nThe number is a Prime :D";
return 0;
}
}
cout << "\nThe number is not a Prime D:";
return 0;
}
Correct me if I'm wrong. I'm a student.
Upvotes: 0
Reputation: 234885
The lowest hanging fruit here is your stopping conditional
i <= x/2
which can be replaced with
i * i <= x
having taken care to ensure you don't overflow an int
.This is because you only need to go up to the square root of x
, rather than half way. Perhaps i <= x / i
is better still as that avoids the overflow; albeit at the expense of a division which can be relatively costly on some platforms.
Your algorithm is also defective for x == 2
as you have the incorrect return value. It would be better if you dropped that extra test, as the ensuing loop covers it.
Upvotes: 5
Reputation: 61
Here is an efficinent way to check prime number.
bool isPrime(int num) {
if(num <= 1) return false;
if (num <= 3) return true;
int range = sqrt(num);
// This is checked so that we can skip
// middle five numbers in below loop
if (num % 2 == 0 || num % 3 == 0)
return false;
for (int i = 5; i <= range; i += 6)
if (num % i == 0 || num % (i + 2) == 0)
return false;
return true;
}
Upvotes: 3
Reputation:
A stander way(maybe..?) is just check from i = 0 to the sqrt(number)
bool isPrime(int num){
if(num == 1) return false;
for(int i = 2;i<=sqrt(num);i++){
if(num % i == 0) return false;
}
return true;
}
Upvotes: 1
Reputation: 127
Here is one efficient way to check a given number is prime.
bool isprime(int n) {
if(n<=1)
return false;
if(n<=3)
return true;
if(n%2==0||n%3==0)
return false;
for(int i=5;i*i<=n;i=i+6) {
if(n%i==0||n%(i+2)==0)
return false;
}
return true;
}
Upvotes: 0
Reputation: 180303
Another inefficiency not yet mentioned is existaP(a, li, (li+ls)/2) + existaP(a, (li+ls)/2+1, ls);
In particular, the problem here is the +
. If you know existaP(a, li, (li+ls)/2)
> 0, then existaP(a, (li+ls)/2+1, ls)
no longer matters. In other words, you're currently counting the exact number of unique factors, but as soon as you know a number has at least two factors you know it's not prime.
Upvotes: 0
Reputation: 139
If the numbers are not too big you could also try to solve this using the sieve of Eratosthenes:
#include <iostream>
#include <array>
using namespace std;
constexpr int LIMIT = 100001;
// not_prime because global variables are initialized with 0
bool not_prime[LIMIT];
void sieve() {
int i, j;
not_prime[2] = false;
for(int i = 2; i < LIMIT; ++i)
if(!not_prime[i])
for(int j = i + i; j < LIMIT; j += i)
not_prime[j] = true;
}
int existaP(int a[], int li, int ls){
if(li==ls)
if(!not_prime[a[li]] == true)
return 1;
else
return 0;
else
return existaP(a, li, (li + ls) / 2) + existaP(a, (li + ls) / 2 + 1, ls);
}
int main(){
int n, a[10001];
cin >> n;
for(int i = 1; i<=n; ++i) cin >> a[i];
sieve();
if(existaP(a,1,n) >= 1) cout << "Y";
else cout << "N";
return 0;
}
Basically when you encounter a prime all the numbers that are a multiple of it won't be primes.
P.S.: Acum am vazut ca esti roman :) Poti sa te uiti aici pentru a optimiza si mai mult algoritmul: https://infoarena.ro/ciurul-lui-eratostene
Upvotes: 0
Reputation: 341
Your code will give a wrong answer if n is 1.
Your time complexity can be decreased to sqrt(n) , where n is the number.
Here is the code
bool isPrime(long int n)
{
if (n == 1)
{
return false;
}
int i = 2;
while (i*i <= n)
{
if (n % i == 0)
{
return false;
}
i += 1;
}
return true;
}
The "long int" will help to avoid overflow.
Hope this helps. :-)
Upvotes: 0