둠치킨
코딩하는 둠치킨
둠치킨

블로그 메뉴

  • 홈
  • 분류 전체보기 (218)
    • BOJ (171)
      • 스택 (14)
      • 큐 (5)
      • 덱 (4)
      • 그래프 (30)
      • 배열 (8)
      • 재귀 (12)
      • 브루트 포스 (2)
      • 그리디 알고리즘 (7)
      • 다이내믹 프로그래밍 (13)
      • 백트래킹 (24)
      • 기하학 (4)
      • 트리 (4)
      • 구현 (14)
      • 수학 (3)
      • 맵 (1)
      • 다익스트라 (2)
      • 누적합 (5)
    • 자료구조 (14)
      • 스택 (3)
      • 큐 (5)
      • 덱 (2)
      • 그래프 (1)
      • 트리 (1)
      • 힙 (1)
      • 정렬 (1)
    • C++ (11)
      • 모두의코드 (2)
      • Effective C++ (3)
      • C++ STL (6)
    • 컴파일러 (1)
    • OS (17)
    • 컴퓨터 구조 (2)
    • Unreal Engine 5 (2)

공지사항

전체 방문자
오늘
어제

인기 글

최근 글

태그

  • BFS
  • boj
  • Bruteforce
  • C
  • C++
  • C++ STL
  • Cache Memory
  • deadlock
  • DFS
  • Effective C++
  • java
  • Mutex
  • next_permutation
  • os
  • Process
  • rotate
  • semaphore
  • spin lock
  • STL
  • STL C++
hELLO · Designed By 정상우.
둠치킨

코딩하는 둠치킨

BOJ/수학

1978번: 소수 찾기 (BOJ C++)

2023. 5. 9. 15:36

1978번:  소수 찾기

사용 언어: C++

 

풀이

아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. 

for(int i=2; i*i<=num; i++)
{
	if(num % i == 0) 
    	flag = false;
}

하지만 귀찮으니 쓰진 않고 알아두기만 하자.

#include <iostream>
using namespace std;

int main(void)
{
	int num;
	int ans = 0;
	cin >> num;
	bool flag;
	while(num--)
	{
		int isPrime;
		flag = true;
		cin >> isPrime;
		if(isPrime == 1)
			continue;
		for(int i=2; i<isPrime; i++)
			if(isPrime % i == 0)
				flag = false;
		if(flag == true)
			ans++;
	}
	cout << ans << '\n';
	
	return 0;
}
저작자표시 (새창열림)

'BOJ > 수학' 카테고리의 다른 글

1990번: 소수인팰린드롬 (BOJ C/C++)  (0) 2022.03.05
1920번: 수 찾기  (0) 2022.01.13
    'BOJ/수학' 카테고리의 다른 글
    • 1990번: 소수인팰린드롬 (BOJ C/C++)
    • 1920번: 수 찾기
    둠치킨
    둠치킨
    코딩 공부를 위한 코딩 블로그 기록 일기

    티스토리툴바