Project Euler — Problem 187

http://projecteuler.net/index.php?section=problems&id=187

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?

library(gmp)
bign <- 10^8
n <- 1:floor((bign -1)/2)
p=1:10000
p = p[as.logical(isprime(p))]
for (i in p) {
	n <- n[as.logical(n %% i)]
}
idx <- as.logical(isprime(n))
allp <- c(p,n[idx])
count <- 0
for (i in allp[allp < sqrt(bign)]) {
	count <- count + length(allp[allp < bign/i])
	allp = allp[-1]
}
print(count)

—-
[1] 17427258
user system elapsed
449.67 72.40 522.87

Not fast enough…

Related Posts

• January 1, 2011 -- Single variable optimization (0)
• December 25, 2010 -- one-dimensional integrals (2)
• December 4, 2010 -- Root finding (4)
• December 1, 2010 -- bubble chart by using ggplot2 (0)
• December 1, 2010 -- The avalanche of publications mentioning GO (0)
• November 30, 2010 -- GOSemSim redesign in terms of S4 classes (0)
• October 20, 2010 -- upgrade R – F77 cause compilation error (0)
• October 19, 2010 -- Listing gene IDs from hyperGTest (0)
• October 15, 2010 -- The S3 OOP system (0)
• October 12, 2010 -- ClusterProfiles (0)

Tags: English, Project Euler, R