[C++][BOJ-소수 관련1978,] 소수찾기, 소인수분해

소수 찾기

백준 소수 찾기 1978

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,num,ans;
	cin>>n;
	ans = n;
	while(n-- ){
		cin>>num;
		if(num<=1) ans--;
		else if (num==2) continue;
		for(int i = 2 ; i <= sqrt(num);i++){
			if( num%i == 0 ){
				ans--;break;
			}
		}
	}
	cout<<ans;
	return 0;
}

다음 문제에 아주 살짝 줄임

---

범위 내 소수 찾기

 

백준 소수 찾기 1929

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;
int main(void){
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i; m<=n ;m++){
		for(i = 2 ; i*i <= m ; i++)
			if(m%i==0) break;
		if( i*i>m && m !=1 )printf("%d\n",m);
	}
	return 0;
}

printf 할때 조건에서 i*i >= m 등호는 불가. (2*2 = 4)

---

 

백준 소수 찾기 1978

 

소스 코드

 

소수 찾기 위해 이중 루프 쓰면 시간 초과 나온다.

 

 

---

 

소인수분해

 

백준 소인수분해 11653

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	vector<int> v;
	int n;
	cin >> n;
	if(n==1) return 0;

	for(int i = 2 ; i<=n;i++){
		while( !(n%i) ){
			cout<<i<<"\n";
			n/=i;
		}			
	}
	return 0;
}