LeetCode #204 CountPrimes. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,소수판별,에라스토스테네스의체,primeNumber,sieveoferastosthenes
I used Sieve of Eratosthenes to get prime number count
소수 개수 구하는데에 Sieve of Eratosthenes (에라스토스의 체) 를 사용해서 풀었다.
풀고보니 약수로 풀때보다 복잡하지는 않았는데, 함수를 쪼개려다가 말려서 오래걸림
퍼포먼스는 상위 40프로 정도로 28ms 나쁘지 않게 나옴
LeetCode #204
Q.
Count the number of prime numbers less than a non-negative number, n.
주어진 양의정수 n 보다 작은 소수의 개수를 세라
e.g.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Process
//Process
//1. Input non-negative integer n
//2. Prepare sieve map
//3. Set false after sifting
// 3.1. Count
//4. Return count
//처리과정
//1. 양의정수 n 을 입력받는다.
//2. 체로 쓸 맵을 만든다.
//3. 해당 인덱스 수로 나누어 지는 수는 false 처리한다.
// 3.1. 처음 수는 카운트로 센다.
//4. 카운트 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// Using Sieve of Erotosthenes // 에라토스테네스의 체(거름막)
int countPrimes(int n) {
int count = 0;
if (n < 2)
return 0;
std::vector<bool> sieveMap(n - 2, true);
int length = sieveMap.size();
for (int i = 0; i < length; ++i)
{
if (sieveMap[i] == true)
{
++count;
for (int j = i + (i + 2); j < length; j = j + (i + 2))
{
sieveMap[j] = false;
}
}
}
return count;
}
};
int main(int args, char *argv[]) {
Solution sln;
cout << sln.countPrimes(10) << endl;
}
Something else you might like...?
2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2018/12/26 - [Programming/Java] - JavaFx, how to show actual size image bigger than pane using scroll, 실제 크기 이미지를 스크롤바 사용하여 보여주는 방법, Java/cpp/kotlin/gui
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법