프로그래머스 | 소수찾기
Algorithm 2019. 8. 26. 11:44문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
nresult
10 | 4 |
5 | 3 |
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
1
2
3
4
5
6
|
public class Solution {
public int solution(int n) {
int answer = 0;
return answer;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
using System;
using System.Linq;
namespace _17
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("소수찾기");
//case 1
//int n = 10;
//result: 4
//case 2
int n = 5;
//result = 3;
var s = new Solution();
var result = s.solution(n);
Console.WriteLine(result);
}
}
public class Solution {
public int solution(int n) {
int answer = 0;
int[] arr = new int[n+1];
for(int i = 2; i<=n; i++){
arr[i] = i;
}
for(int i = 2; i<=n; i++){
for(int j = 2; j<=n; j++){
if(arr[j] != i && arr[j] % i == 0){
arr[j] = 0;
}
}
}
foreach(var prime in arr){
Console.Write(prime + " ");
}
Console.WriteLine();
return answer;
}
}
}
|
체크할 때, 모든 수를 다 돌면서 체크할 필요 없이 배수만큼만 반복문을 돌게하는 것이다.
그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다.
(왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다)
출처: https://marobiana.tistory.com/91
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
using System;
using System.Linq;
namespace _17
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("소수찾기");
//case 1
int n = 10;
//result: 4
//case 2
//int n = 5;
//result = 3;
//case 3
//int n = 100;
//result = ?
var s = new Solution();
var result = s.solution(n);
Console.WriteLine(result);
}
}
public class Solution {
public int solution(int n) {
int answer = 0;
int[] arr = new int[n+1];
for(int i = 2; i<=n; i++){
arr[i] = i;
}
for(int i = 2; i<=n; i++){
if(arr[i] == 0) continue; //배수인지 체크
for(int j = i + i ; j<=n; j += i){
if(arr[j] == 0) continue;
Console.WriteLine(arr[j] + " ---> 0");
arr[j] = 0;
}
}
Console.WriteLine();
Console.WriteLine("*******************");
foreach(var num in arr){
Console.Write(num + " ");
if(num != 0){
answer++;
}
}
Console.WriteLine();
Console.WriteLine("*******************");
//answer = arr.ToList().Where(x=>x != 0).Count();
return answer;
}
}
}
|
'Algorithm' 카테고리의 다른 글
프로그래머스 | 조이스틱 | 그리디 알고리즘 (0) | 2019.08.26 |
---|---|
프로그래머스 | JadenCase 문자열 만들기 (0) | 2019.08.26 |
프로그래머스 | 평균구하기 (0) | 2019.08.26 |
프로그래머스 | 문자열 내 마음대로 정렬하기 (0) | 2019.08.26 |
프로그래머스 | Collatz(콜라츠) 추측 (0) | 2019.08.26 |