11086 - Composite Prime

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 11086 - Composite Prime

Post by Jehad Uddin » Thu Nov 11, 2010 4:04 am

219760

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

Re: 11086 - Composite Prime

Post by Ahmad » Sun Sep 11, 2011 10:27 pm

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

Post by monteeishere » Thu Nov 13, 2014 4:47 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11086 - Composite Prime

Post by lighted » Thu Nov 13, 2014 5:22 pm

I made precalculation of all composite primes in boolean array composite[1048576] 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

Post Reply

Return to “Volume 110 (11000-11099)”