c++ - 两个素数等于偶数

Question

给定一个偶数 n>2，求和为 n 的素数。必须使用找到素数的函数。

也许可以开始这样的事情？：

for (int i = 2; i < n; i++)
{
    if (IsPrime(i) && IsPrime(n - i))
        break;
}

Answer 1

这对我有用..

public ArrayList<Integer> primesum(int A) {

    ArrayList<Integer> result = new ArrayList<Integer>();
    if(A < 2)
        return result;

    int first = 2;
    int second = A - first; 
    while(first <= second){
        second = A - first;

        if(isPrime(second) == true && isPrime(first)){
            result.add(first);
            result.add(second);
            return result;
        }
        first++;
    }

    return result;

}


public boolean isPrime(int n)
{
    if(n==1)
        return false;
    for(int i=2;i<=Math.sqrt(n);i++) {
        if(n%i==0)
            return false;
        }
    return true;
}

Answer 2

我只是给你一个提示，而不是整个解决方案，这将是起点！

这是可能的解决方案之一，而不是解决方案：

首先，定义一个检查数字是否为素数的函数：

bool isPrime(const unsigned& number) {
  for (unsigned i = 2; i < number; i++) {
     if (number % i == 0) {
       return false;
     }
   }
  return true;
 }

还定义：

struct PrimeSum {
  unsigned first;
  unsigned second; 
 };

PrimeSum searchPrimeAddend(const unsigned& number, const vector<unsigned>& v) {
   // your code to find two number iterating the vector 
}

在你的主要：

int main(const int argc, const char* argv[]) {
  const unsigned N = 13;
  std::vector<unsigned> primeList;
  for (unsigned i = 3; i < N; i += 2) {
    if (isPrime(i)) {
       primeList.push_back(i);
    }
  }
 PrimeSum primes = searchPrimeAddend(N, primeList);
}

Answer 3

我认为这是一个家庭作业，所以我会给你一些开始的提示：

1) 要检查一个数 N 是否为素数，您可以迭代到 N/2 并在找到它的倍数时中断。如果您不太关心空间和时间的复杂性，那么嵌套的 for 循环将是最简单的解决方案。

Answer 4

这有效，它是 C++

bool isPrime(int number){
    if (number == 1)
        return false;

    if (number == 2)
        return true;

    for (int i = 2; i <= number / 2; ++i)
        if (number % i == 0)
            return false;

    return true;
}

vector<int> Solution::primesum(int A) {    
    std::vector<int> vect;
    int pivot = A / 2; // the prime numbers cannot cross each other in the middle

    // keep j less than the i. i will be the lower bound of the number and
    // j will be the higher bound
    int j = A-2;
    for (int i = 2; i <= pivot && j >= pivot; i++, j--){
        if (isPrime(i) && isPrime(j)){
            vect.push_back(i);
            vect.push_back(j);
            return vect;
        }
    }

    return vect;
}

Answer 5

伪代码

• 找到直到 n 的所有素数并填充一个容器（按插入或容器排序）
• 对于容器获取正向迭代器“向上”和反向迭代器“向下”
• while (up!=end && down!=rend && *up<=*down)
  • 总和 = *上 + *下
  • 如果总和 == n
    • 保存对 // 找到
    • ++向上
  • 否则，如果总和 > n
    • ++下
  • 否则，如果总和 < n
    • ++向上

这给你留下了一些 C++ 作业

不同的解决方案（单次运行可能更有效）

• 找到 n/2 以内的所有素数并填充一个容器（按插入或容器排序）
• 对于容器前进迭代器“向上”
• 而（向上！=结束）
  • 其他 = n - *向上
  • if is_prime(其他)
    • 保存对 *up，其他
  • ++向上