•  05-07-2019
  •  | 
  •  

문제

나는 임의의 숫자 범위를 가지고 있습니다.범위는 실제로 사용자가 결정하지만 최대 1000개의 정수입니다.그것들은 다음 위치에 배치됩니다:

vector<int> n

값은 다음과 같이 삽입됩니다.

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

소수가 아닌 모든 값을 찾기 위해 별도의 함수를 만들고 있습니다.여기에 내가 지금 가지고 있는 것이 있지만 시리즈에서 소수와 합성을 모두 얻었기 때문에 그것이 완전히 잘못된 것임을 압니다.

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

이 방법은 일반적으로 0부터 1000까지의 일련의 숫자가 있을 때 효과가 있었지만 지금은 숫자가 순서에 맞지 않거나 중복되면 작동하지 않는 것 같습니다.벡터에서 소수가 아닌 숫자를 찾는 더 좋은 방법이 있습니까?다른 벡터를 만들고 n개의 숫자로 채우고 그런 식으로 소수가 아닌 값을 찾고 싶은 유혹이 있지만 그게 비효율적일까요?

좋습니다. 범위는 0-1000이므로 0-n으로 정렬된 벡터를 만든 다음 체를 사용하여 소수를 찾는 것이 더 쉬운지 궁금합니다. 점점 더 가까워지고 있나요?

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}
도움이 되었습니까?

해결책

이 코드에서 :

if(i % v[j] == 0)
  cout << v[j] << endl;

당신은 당신의 색인을 테스트하여 V [j]로 나눌 수 있는지 확인하고 있습니다. 나는 당신이 다른 방법으로 그것을하려고했다고 생각합니다.

if(v[j] % i == 0)

지금, 당신은 i의 랜덤 디바이저를 인쇄하고 있습니다. 당신은 프라임이 아닌 것으로 알려진 임의의 숫자를 인쇄하지 않습니다. 또한 출력에 복제물이있을 것입니다. 아마도 괜찮을 것입니다.

다른 팁

우선, Knuth는 먼저 말했습니다. 조기 최적화는 많은 버그의 원인입니다. 느린 버전을 먼저 만든 다음 더 빨리 만드는 방법을 알아냅니다.

둘째, 외부 루프의 경우 실제로 n이 아닌 SQRT (n)로 이동하면됩니다.

기본적으로, 당신은 관련이없는 숫자가 많기 때문에 각 숫자에 대해 그것이 프라임인지 확인해야합니다.

미리 숫자의 범위를 알고 있다면 모든 소수를 생성 할 수 있습니다. ~할 수 있다 해당 범위 (또는 SQRT)에서 발생하고 생성 된 프라임 중 하나에 의해 컨테이너의 모든 숫자를 테스트하십시오.

프라임 생성은 Erathostenes Sieve에 의해 가장 잘 이루어집니다. 그 알고리즘에 대한 많은 예제를 찾을 수 있습니다.

당신은 a를 사용해야합니다 프라임 체. 체를 만들기위한 최대 숫자를 알아야합니다 (O(n)) 그런 다음 해당 범위에서 일련의 프라임을 만들 수 있습니다 (O(max_element) 또는 문제가 나타납니다 O(1000) == O(1))) 및 각 숫자가 프라임 세트에 있는지 확인하십시오.

당신의 코드는 단지 명백한 잘못입니다. 먼저, i % v [j] == 0을 테스트하고 있는데, 이는 뒤로이며 모든 숫자를 얻는 이유를 설명합니다. 둘째, 출력은 (깨진) 분할 성 테스트에 실패 할 때마다 각 입력 번호를 테스트하고 출력 할 때 중복을 포함합니다.

기타 제안 :

n을 벡터의 최대 값으로 사용하고 벡터의 요소 수는 혼란스럽고 무의미합니다. 벡터의 요소 수를 전달할 필요가 없습니다. 벡터의 크기를 쿼리합니다. 그리고 당신은 최대를 상당히 빨리 알아낼 수 있습니다 (그러나 미리 알고 있다면 그것을 전달할 수도 있습니다).

위에서 언급했듯이 SQRT (N)로만 테스트하면됩니다. [여기서 N은 Vecotr의 최대 값입니다

체를 사용하여 모든 프라임을 최대 n으로 생성 한 다음 위에서 제안한대로 입력 벡터에서 해당 값을 제거 할 수 있습니다. 특히 프라임을 어딘가에 저장하는 경우 더 빠르고 이해하기 쉬울 수 있습니다.

각 숫자를 개별적으로 테스트하려면 (사용, 추측 및 역 체가) 각 숫자를 개별적으로 테스트하는 것이 좋습니다. IMHO 작성 방식보다 이해하기가 더 쉽습니다. K <N으로 각 숫자를 k <n으로 테스트하면 k k <n입니다.

당신이 구현하려는 체의 아이디어는 당신이 프라임 (2)에서 시작하고 해당 숫자의 멀티 트리트를 교차한다는 사실에 달려 있습니다. 따라서 프라임 "2"에 의존하는 모든 숫자는 미리 배제됩니다.

이는 모든 비 프라임이 프라임으로 인수 될 수 있기 때문입니다. 반면, 프라임은 1으로 나누거나 스스로 나누지 않는 한 모듈로 0과 나눌 수 없습니다.

따라서이 알고리즘에 의존하려면 알고리즘 의이 속성을 실제로 복원해야합니다.

코드는 많은 문제가있는 것 같습니다.

  1. 숫자가 프라임인지 비 프라임인지 테스트하려면 v [j] % i == 0을 확인해야합니다.
  2. 당신은 당신의 번호가 그 자체로 나누고 있는지 확인하지 않았습니다.
  3. 당신은 계속해서 당신의 번호를 반복해서 확인합니다. 그것은 매우 비효율적입니다.

다른 사람들이 제안한 것처럼, 당신은 에라 토스 텐스의 체와 같은 일을해야합니다.

따라서 문제에 대한 의사 C 코드는 (아직 컴파일러를 통해이를 실행하지 않았으므로 구문 오류를 무시하십시오.이 코드는 알고리즘을 설명하는 것입니다).

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}

먼저 숫자를 정렬하는 것이 좋은 시작일 수 있습니다. nLogN 시간 안에 그렇게 할 수 있습니다.그것은 숫자가 소수인지 찾는 문제인 다른 문제에 작은 추가 사항입니다.
(실제로 이와 같은 작은 숫자 세트를 사용하면 벡터/세트 크기의 복사본을 사용하여 훨씬 빠르게 정렬을 수행하고 해시/버킷 정렬 등을 수행할 수 있습니다)

그런 다음 세트에서 가장 높은 숫자를 찾습니다. (숫자는 무제한일 수 있다고 가정합니다. 정렬할 때까지 상한선을 알 수 없습니다. 또는 최대값을 찾기 위해 단일 패스를 수행합니다.)

그런 다음 체를 가지고 가십시오 - 다른 사람들이 말했듯이

제레미는 옳습니다. 기본적인 문제는 당신입니다 i % v[j] 대신에 v[j] % i.

이 시도:

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

모든 숫자로 나누려고 시도하기 때문에 최적이 아닙니다. v[j] 의 제곱근 대신 v[j]. 그리고 그것은 단지 프라임 대신 모든 숫자로 분할을 시도하고 있습니다.

그러나 그것은 효과가있을 것입니다.

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