프로그래머스 C# 소수 찾기(제곱근, 루트, 2~n, 2~root(n))

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        int sosu = 0;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i%j == 0)
                {
                    sosu++;
                }
            }
            
            if(sosu == 2)
            {
                answer++;
            }
            sosu = 0;
        }
        
        return answer;
    }
}

 

///이렇게 노가다로 하면 시간 때문에 안된다.

 

public class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int j=2; j<=n; j++)
        {
            if(isPrime(j) == true)
            {
                answer++;
            }
        }    
        
        return answer;
    }
    
    public bool isPrime(int num)
    {
        for(int i=2; i*i<=num; i++)
        {
            if(num%i == 0) return false;
        }
        return true;
    }
}