专栏首页流川疯编写程序的艺术leetcode 204题求素数个数

leetcode 204题求素数个数

Description:

Count the number of prime numbers less than a non-negative number, n

提示晒数法:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

https://primes.utm.edu/howmany.html

别人的代码:

int countPrimes(int n) {
    if (n<=2) return 0;
    vector<bool> passed(n, false);
    int sum = 1;
    int upper = sqrt(n);
    for (int i=3; i<n; i+=2) {
        if (!passed[i]) {
            sum++;
            //avoid overflow
            if (i>upper) continue;
            for (int j=i*i; j<n; j+=i) {
                passed[j] = true;
            }
        }
    }
    return sum;
}

我的代码:

// countprime.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include <iostream>
#include <math.h>
#include<vector>
using namespace std;

int countPrimes1(int n) 
{
	int temp = 0;
	if (2 >= n) return 0;

	bool* primes = new bool[n];
	for (int i = 2; i < n; ++i)
		primes[i] = true;

	int sqr = (int)(sqrt((double)(n - 1)));
	for (int i = 2; i <= sqr; ++i)
	{
		if (primes[i])
		{
			temp++;
			for (int j = i * i; j < n; j += i)
				primes[j] = false;
		}
	}

	int sum = 0;
	for (int i = 2; i < n; ++i)
		sum += (primes[i]) ? 1 : 0;

	/*cout<<temp;*/
	delete[] primes;

	return sum;
}


int countPrimes(int n)
{
	if (n<=2)return 0;

	int sum = 0;
	int sqr = (int)(sqrt((double)(n - 1)));

	vector<bool> prime(n,0);

	for(int i = 2; i < n; ++i)
		prime[i] = 1;

	for(int i =2; i <= sqr; ++i)
	{
		if(prime[i]==1)
		{
			//sum++;
			for(int j = i*i; j < n; j = j+i)
				prime[j] = 0;
		}

	}

	for(int i = 2;i < n; ++i)
		sum += prime[i] ? 1 : 0;


	return sum;
}

int _tmain(int argc, _TCHAR* argv[])
{
	


	cout<<countPrimes(5)<<endl;
	
	cout<<countPrimes1(3)<<endl;

	getchar();
	return 0;
}

超时代码:

int countPrimes(int n)
    {
        int sum = 0;
        for(int i = 0 ;i<=n;i=i+2)
        {
            int j = 2;
            int temp = sqrt(i);
            for(;j<=temp;j=j+1)
            {
                if((i%temp)==0)
                {break;}
                sum++;
            }
        }
            
        
        return sum;
    }

纪念一下首次AC

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode 88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one so...

    用户1539362
  • 欢聚时代笔试题,滴滴出行编程题

    intel 笔试: 1.单链表逆置,双向链表删除 2.层次遍历二叉树 3.rand4()生成rand9() 4.非常多的各种指针操作。

    用户1539362
  • leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

    Given a string, find the length of the longest substring without repeating chara...

    用户1539362
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津
  • 15.瀑布流、测量

    六月的雨
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear

扫码关注云+社区

领取腾讯云代金券