11086 - Composite Prime

[Jehad Uddin]

219760

[Ahmad]

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]

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]

I made precalculation of all composite primes in boolean array composite[1048576] and then processed(calculated) input.