半质数优化有关问题
半质数优化问题
//则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。我们的问题是，输入两个正整数x<=y，
//问[x,y]之间有多少个半质数？ 输入:x,y 输出:[x,y]之间有多少个半质数。 输入数据范围 1<=x<=y<=2000000。
//祝所有挑战的Heros 2014年情人节、元宵节快乐
要求程序运行在3s以内
------解决方案--------------------
// 我机器上是46ms
// 暴力代码有注释
// 预处理解法得在网上搜索 贾志鹏线性筛
本帖最后由 a120705230 于 2014-02-17 23:27:37 编辑
//质数是大家熟知的概念，我们定义一个半质数的概念：如果一个数恰好是两个质数的乘积（可以相同），//则称它为半质数。前几个半质数是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。我们的问题是，输入两个正整数x<=y，
//问[x,y]之间有多少个半质数？ 输入:x,y 输出:[x,y]之间有多少个半质数。 输入数据范围 1<=x<=y<=2000000。
//祝所有挑战的Heros 2014年情人节、元宵节快乐
using System;
public class Test
{
public static int howmany(int x, int y)
{
int count = 0;
for (int i = x; i < y; i++)
{
if (isSemiPrimer(i))
{
count++;
}
}
return count;
}
public static void Main()
{
DateTime dateStart = DateTime.Now;
Console.WriteLine(howmany(1, 2000000));
TimeSpan span = DateTime.Now - dateStart;
Console.WriteLine(span.TotalSeconds.ToString());
}
public static bool isPrime(int x)
{
for (int i = 2; i <= Math.Sqrt((double)x); i++)
{
if (x % i == 0)
{
return false;
}
}
return true;
}
public static bool isSemiPrimer(int x)
{
for (int i = 2; i <= Math.Sqrt((double)x); i++)
{
if (x % i == 0)
{
return isPrime(x / i) && isPrime(i);
}
}
return false;
}
}
要求程序运行在3s以内
------解决方案--------------------
// 我机器上是46ms
// 暴力代码有注释
// 预处理解法得在网上搜索 贾志鹏线性筛
#include <iostream>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <cassert>
using namespace std;
const int maxn = 2000000;
int plist[1000000], mask[maxn+1], pcnt;
int dp[maxn+1];
// 暴力代码
bool check(int n)
{
if (n < 2) return 0;
int pc = 0; // 出现过的素数的1次方的个数
for (int i = 2; ;++i)
{
const int t = i * i;
if (t > n) break;
int c = 0;
while (n % i == 0) n /= i, ++c;
if (c == 0) continue;
if (c == 2)
{
return pc == 0 && n == 1; // 本身是素数的平方
}
else if (c == 1)
{
++pc;
}
else
{
return 0;
}
}
if (n > 1) ++pc;
return pc == 2;
}
void init()
{
for (int i = 2; i <= maxn; ++i)
{
if (mask[i] == 0)
plist[pcnt++] = i, dp[i] = 1;
for (int j = 0; j < pcnt; ++j)
{
const int p = plist[j];
const int t = p * i;
if (t > maxn) break;
mask[t] = 1;
if (i % p == 0)
{
dp[t] = 0;
break;
}
else
{
dp[t] = dp[i] == 0 ? 0 : dp[i] + 1;
}
}
}