Problem #187 says:

A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

How many composite integers, n < 10^(8), have precisely two, not necessarily distinct, prime factors?

This is a simple brute force attempt. It generates all primes up to the square root of 10^8 and then just goes through each number from 3 to 10^8 and factors it using the generated primes. This approach takes about 10 minuets to provide the answer. There are several methods for solving this problem that can reduce it to under 10 seconds that I might try to code later. Alternatively using parts from previous problems this problem could be done in parallel with f# without too much work using PSeq.filter.

Solution provided in c++ written using openSuse 11.3, geany, and gcc. I’m pretty rusty on writing code in c++ so excuse any glaring inefficiencies.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

using namespace std;

unsigned int newt_sqrt(unsigned int input)
{
	int nv, v = input>>1, c = 0;
	if (!v)
	return input;
	do
	{
		nv = (v + input/v)>>1;
		if (abs(v - nv) <= 1)
			return nv;
		v = nv;
	}
	while (c++ < 25);
	return nv;
}

vector<int> Primes (int max)
{
	vector<int> primes;
	primes.push_back(2);
	bool div = false;
	for(int i = 3; i <= max;i++)
	{
		int sqrp = newt_sqrt(i) + 1;
		for(unsigned int p = 0; p < primes.size(); p++)
		{
			int d = primes[p];
			if (d > sqrp)
				break;
			if (i % d == 0)
				div = true;
		}
		if (!div)
			primes.push_back(i);
		div = false;
	}
	return primes;
}
int Factors(int num, vector<int>  const  &primes, int factors)
{
	if (factors > 2)
		return 6000;
	bool divided = false;
	for (unsigned int i = 0; i < primes.size(); i++)
	{
		if (num % primes[i] == 0)
		{
			factors++;
			num = num / primes[i];
			divided = true;
			break;
		}
	}
	//if no divisions happen we've come across a prime larger than our
	//prime set. we just mark it as a factor and move along
	if (!divided)
	{
		num = 1;
		factors ++;
	}
	if (num != 1)
		return Factors(num,primes,factors);
	else
		return factors;
}
int SemiPrime (int max, vector<int> const &primes)
{
	int Answer = 0;
	for (int i = 3; i <= max; i++)
	{
		if (Factors(i,primes,0) == 2)
			Answer++;
	}
	return Answer;
}
int main(int argc, char** argv)
{
	vector<int> p = Primes(10000);
	int max = 100000000;
	int Answer= SemiPrime(max,p);

	cout << "Answer is :: " << Answer << endl;
	return 0;
}