## 11086 - Composite Prime

Moderator: Board moderators

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11086 - Composite Prime

219760

New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### Re: 11086 - Composite Prime

if you really understand what sieve is doing then it's a very easy problem ...
just do sieve 2 times ... (more explanation would be spoiler )
i just reimplemented sieve with small changes and i got rank 5 in this problem after small optimization of my code ...

monteeishere
New poster
Posts: 1
Joined: Thu Nov 13, 2014 4:46 pm

### Re: 11086 - Composite Prime

Getting TLE Code: Select all

``````#include <iostream>
#include <vector>
#include <math.h>
#include <cstring>
using namespace std;
#define MAX 1048576
vector<int> primes;

void markMultiples(bool arr[], int a, int n)
{
int i = 2, num;
while ((num = i*a) <= n)
{
arr[num - 1] = 1; // minus 1 because index starts from 0.
++i;
}
}
void SieveOfEratosthenes(int n)
{
if (n >= 2)
{
bool* arr = new bool[n];
memset(arr, 0, n);

for (int i = 1; i<n; ++i)
{
if (arr[i] == 0)
{
primes.push_back(i + 1);
markMultiples(arr, i + 1, n);
}
}
}
}

bool isPrime(int number)
{
if (number == 2)
return true;
if ((number % 2) == 0)
return false;
for (int i = 3; i < number; i += 2)
{
if (number % i == 0)
return false;
}
return true;
}
bool isCompositePrime(int number)
{
if (isPrime(number))
return false;
for (int i = 0; primes[i] <= sqrt(number); i++)
{
int value = number / primes[i];
if (value*primes[i] == number && isPrime(value))
return true;
}
return false;
}
int main()
{
SieveOfEratosthenes(sqrt(MAX));
int size;
vector<int> outputs;
while (cin >> size)
{
vector<int> inputs;
int input,output = 0;
for (int i = 0; i < size; i++)
{
cin >> input;
if (isCompositePrime(input))
output++;
}
outputs.push_back(output);
}
for (int i = 0; i < outputs.size(); i++)
cout << outputs[i] << endl;
return 0;
}``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11086 - Composite Prime

I made precalculation of all composite primes in boolean array composite and then processed(calculated) input. A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman