전체 글
-
백준 16563번 (어려운 소인수분해) c++백준 문제 2021. 8. 31. 18:21
문제 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 단순히 백준 11653(소인수분해)문제와 비슷한줄 알고 바로 똑같이 코드를 작성해 주었습니다. #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int n; cin >> n; while (n--) { int k; cin >> k; for (int i = 2; i * i
-
백준 2960번(에라토스테네스의 체)c++백준 문제 2021. 8. 30. 16:17
문제 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 기존 에라토스테네스에서 응용 문제입니다. 에라토스테네스는 소수를 제외하고 합성수를 지웠는데 여기 문제에서는 소수까지 지워서 임의의 정수 k를 입력받아 k 번째 지운 수를 출력해주는 문제입니다. int n, k; cin >> n >> k; int cnt = 0; bool flag = false; 먼저 어디까지 소수를 판별할 n 과 몇번째에서 지우는지 k 를 입력 받습니다. 변수 cnt를 선언해줘서 숫자를 지울때마다 cnt가 올라가게 해서 cnt가 k가 되면 그 수를 출려하게끔하는 장치입니다. bool형 flag는 cnt가 k로 되면 더이상 나머지..
-
소수 판별(1) (C언어)Sogang ICPC (기초) 2021. 8. 30. 14:37
소수는 1과 자기자신을 제외하고 나누어 떨어지는 수가 없는 수입니다. 먼저 단순히 2부터 시작해서 하나씩 나누어 떨어지는지 판별하는 코드 입니다. #include int isprimeNumber(int x) { //소수 판별 (시간복잡도가 많이 듬) for (int i = 2; i < x; i++) { if (x % i == 0) return 0; //합성수 } return 1; //소수 } int main(){ int n; scanf("%d",&n); if(isprimeNumber(n)==1) printf("소수"); else printf("합성수); return 0; } 보시는 바와 같이 for문에서 i가 2부터 x-1 까지 순서대로 x와 나누어 떨어지는지 확인합니다. 물론 n이 작은 수면 상관 없지..
-
최대공약수 , 최소공배수(유클리드 호제법)C언어Sogang ICPC (기초) 2021. 8. 30. 14:33
두 수의 최대 공약수를 구하는 방법 (유클리드 호제법)을 공부해 봤습니다. 두수 x, y 가 있을때, y가 0이 될때 까지 재귀함수로 구현해주면 됩니다. 예를들어 x가 25 y가 100이면 두수의 최대 공약수를 구하려면 사진과 같이 이루어지면 된다. 재귀 함수를 이룰 때는 y자리의 100은 x자리로 이동하고 x자리의 25는 y로 나누어 나머지가 y가 된다. 계속 재귀함수를 수행하면서 y가 0이 되었을때, x 자리의 있는 수가 최대공약수 이다. 이를 코드로 구현해보자 #include int gcd(int x, int y){ if (!y) //y==0 return x; return gcd(y, x % y); } int main(){ int a, b; scanf("%d %d",&a,&b); printf("%d..