사용자가 정의한 양의 소수를 어떻게 생성합니까?

StackOverflow https://stackoverflow.com/questions/2415033

  •  19-09-2019
  •  | 
  •  

문제

사용자 입력을 기반으로 소수를 생성하려고 합니다.이것이 내가 지금까지 가지고 있는 것이지만 그것을 알아낼 수 없는 것 같습니다.

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for
도움이 되었습니까?

해결책

루프 구조를 보면 결과가 왜 쉽게 잘못되었는지 확인할 수 있어야합니다. 손으로 그들을 통과하십시오 (오래 걸리지 않음).

현재 결과를 얻는 이유는 외부 루프의 모든 반복이 아니기 때문입니다 (x < numberOfPrimes) 결과를 생성합니다 - 내부 루프가 구조화되는 방식으로 인해 상당히 몇 가지 반복을 건너 뜁니다.

실제로해야 할 일은 내부 루프를 재구성하는 것입니다. 가장 안쪽 루프는 잘 작동하며 소수를 감지해야합니다. 그러나 두 번째 루프는 아직 테스트되지 않은 숫자 만 테스트해야합니다. 또한 소수를 찾으면 반복을 중지해야합니다.

다른 팁

코드를 더 잘 구성해야 합니다. 지금 하는 방식은 정말 지저분합니다.방법이 있다 IsPrime(int x) 다음과 같은 경우 true를 반환합니다. x 소수이고 그렇지 않으면 거짓입니다.

그런 다음 생성하려면 numberOfPrimes 소수라면 다음과 같이 할 수 있습니다:

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

또는 에라토스테네스의 체, 훨씬 빠른 방법입니다.

숫자인지 확인하려면 x 소수인지 아닌지, 다음 사이의 모든 인수를 시도해 보세요. 2 그리고 Sqrt(x).왜? Sqrt(x)?왜냐하면 만약에 a*b = x, 그 다음에 x / b = a 그리고 x / a = b, 그래서 모든 것을 두 번 확인하고, 올라갔을 때 하지 말아야 할 것도 확인하게 됩니다. x / 2 또는 x.

그래서 당신이 IsPrime(x) 기능:

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

하지만 에라토스테네스의 체를 사용하는 것이 훨씬 빠르기 때문에 사용하는 것이 좋습니다.짝수는 2를 제외하고는 결코 소수가 아니기 때문에 짝수를 확인하지 않도록 최적화할 수도 있습니다(체와 순진한 방법 모두에서).x = 2를 극단적인 경우로 처리한 다음 다른 모든 숫자(3, 5, 7, 9, 11 등)를 확인하기 시작합니다.

당신이 찾고있는 것은 "Eratosthenes의 체"입니다. 사람들의 숙제를하지 않기 때문에 이것이 내가 당신에게 줄 유일한 단서입니다. 알고리즘은 인터넷에서 쉽게 찾을 수 있습니다.

다음 소수 (x)는 s <= sqrt (x)와 같은 모든 프라임에 의해 결정될 수없는 숫자입니다. 따라서 기능을 사용할 수 있습니다 

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

그리고 당신이 같은 소수를 얻을 수있는 것보다

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

codethinked.com에서 복사했습니다

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}

1. 변수의 이름을 바꿉니다.

첫째, 이것이 숙제라면 당신은 무의미한 가변 이름을 가지고 있기 때문에 나쁜 자국을 얻게됩니다 (선생님은 소금의 가치가 있다면) numberOfPrimes 잘못되었고 이름이 지정되어야합니다 requiredNumberOfPrimes. 내가이 변수를 볼 때 나는 '이것이 그가 원하는 수, 얼마나 많은 것을 찾았 는가?'라고 스스로에게 묻습니다.

둘째, 그것은 당신이 어디에서 잘못 될지 이해하는 데 도움이 될 것입니다. 변수는 자신이 나타내는 것에 따라 논리적으로 명명되어야합니다. 변수가 나타내는 것을 설명 할 수 없다면 (예 : A & B) 아마도 당신은 그들과 함께 무엇을하고 있는지 설명 할 수 없을 것입니다.

2. 루프를보십시오.

for (int x = 0; x < numberOfPrimes; x++)

루프의 구조는입니다 (initialise; 'should I continue?'; 'each loop do this'). 따라서 루프에서

  • 당신은 X가 동일하거나 큰 것까지 계속되고 있습니다. numberOfPrimes*.
  • 루프를 통과 할 때마다 1에 1을 추가합니다. x.

이것이 당신이하고 싶은 일이라고 확신합니까? x 찾은 프라임 수를 나타내는 것으로 보입니다. 루프를 시작할 때보다 프라임을 찾을 때 점점 씩 증가하지 않겠습니까?

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

당신은 2와 사이의 각 정수를보고 있습니다 x, 포함한. 그리고 각 정수에 대해 a, 당신은 사이의 모든 정수를보고 있습니다 a 그리고 2 포괄적. 이 정수들과 무엇을 할 건가요?

최상위 루프 ( x 루프), 당신은 당신의 시작할 것입니다 a 처음부터 루프하고, 당신이 당신의 a 루프를 시작합니다 b 처음부터 루프.

그래서 만약 x 10, 당신은 한 번 (a = 2)를 통과 한 다음 다시 (a = 2, a = 3)를 통과 한 다음 다시 (a = 2, a = 3, a = 4)를 통과합니다. 그 다음에...

3. 결과를 콘솔에 쓰지 않고 결과를 수집하십시오.

var primes = new List<int>();

너무 쉽습니다. 프라임을 찾으면 primes.Add(a);. 그런 다음 얼마나 많은 프라임을 찾았는지 알 수 있습니다 (primes.Count), 프라임 목록을 사용하여 다음 프라임을 효율적으로 결정할 수 있으며 필요한 경우 나중에 목록을 사용할 수 있습니다.

Ithe Loops를 정렬하면 B <sqrt (a)를 확인하면 더 높고 다른 요인을 먼저 찾았을 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top