0

我正在解决项目 euler 的一个问题，该问题要求我找到 200 万以下的所有素数之和。我试图实现阿特金的筛子，奇怪的是它把像 65,85 这样的数字设置为素数。我看了一天多的代码和算法，但找不到任何问题。我确定它一定很愚蠢，但我找不到它。在此先感谢我正在使用 Visual Studio Express 2012。

这是代码：

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
#include <conio.h>

 int main(){
    long long int limit,n;
    std::cout<<"Enter a number...."<<std::endl;
    std::cin>>limit;

    std::vector<bool> prime; 


    for(long long int k=0;k<limit;k++){ //sets all entries in the vector 'prime' to false
        prime.push_back(false);
    }

    long long int root_limit= ceil(sqrt(limit));

    //sive of atkin implementation
    for(long long int x=1;x<=root_limit;x++){

        for(long long int y=1;y<=root_limit;y++){

            n=(4*x*x)+(y*y);
            if(n<=limit && (n%12==1 || n%12==5)){
                prime[n]=true;
            }

            n=(3*x*x)+(y*y);
            if(n<=limit && n%12==7){
                prime[n]=true;
            }

            n=(3*x*x)-(y*y);
            if(x>y && n<=limit && n%12==11){
                prime[n]=true;
            }
        }
    }


    //loop to eliminate squares of the primes(making them square free)
    for(long long int i=5;i<=root_limit;i++){
        if(prime[i]==true){
            for(long long int j=i*i;j<limit;j+=(i*i)){
                prime[j]=false;
            }
        }
    }
    unsigned long long int sum=0;

    //print values to a seperate text file 
    std::ofstream outputfile("data.txt");
    outputfile<<"2"<<std::endl;
    outputfile<<"3"<<std::endl;
    for(long long int l=5;l<limit;l++){
        if(prime[l]==true){
            sum+=l;
            outputfile<<l<<std::endl;;
        }
    }

    outputfile.close();


    std::cout<<"The sum is...."<<sum+5<<std::endl;

    prime.clear();
    return 0;
}

和她的 data.txt 我指出了一些错误

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 65<-- 67 71 73 79 83 85<-- 89 91 97 101 103 107 109 113 127 131 137 139 143 145<---- 149 151 157 163 167 173 179 181 185<---- 191 193 197 199 205 211 221 223 227 229 233 239 241 247 251 257 259 263 265 269 271 277 281 283 293 299 305 307 311 313 317 331 337 347 349 353 359 365 367 373 377 379 383 389 397 401 403 407 409 419 421 427 431 433 439 443 445 449 457 461 463 467 479 481 485 487 491 493 499 503 505 509 511 521 523 533 541 545 547 557 559 563 565 569 571 577 587 593 599 601 607 611 613 617 619 629 631 641 643 647 653 659 661 671 673 677 679 683 685 689 691 697 701 703 709 719 727 733 739 743 745 751 757 761 763 767 769 773 785 787 793 797 803 809 811 821 823 827 829 839 851 853 857 859 863 865 871 877 881 883 887 901 905 907 911 919 923 929 937 941 947 949 953 965 967 971 977 983 985 991 997 1009 1013 1019 1021 1027 1031 1033 1037 1039 1049 1051 1061 1063 1067 1069 1073 1079 1087 1091 1093 1097 1099 1103 1105 1109 1117 1123 1129 1145 1147 1151 1153 1157 1159 1163 1165 1171 1181 1187 1189 1193 1199 1201 1205 1213 1217 1223 1229 1231 1237 1241 1249 1259 1261 1267 1277 1279 1283 1285 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1339 1345 1351 1361 1367 1373 1381 1385 1387 1391 1399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 19993 1199 1201 1205 1213 1217 1223 1229 1231 1237 1241 1249 1259 1261 1267 1277 1279 1283 1285 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1339 1345 1351 1361 1367 1373 1381 1385 1387 1391 1399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 19993 1199 1201 1205 1213 1217 1223 1229 1231 1237 1241 1249 1259 1261 1267 1277 1279 1283 1285 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1339 1345 1351 1361 1367 1373 1381 1385 1387 1391 1399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 199961 1267 1277 1279 1283 1285 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1339 1345 1351 1361 1367 1373 1381 1385 1387 1391 1399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 199961 1267 1277 1279 1283 1285 1289 1291 1297 1301 1303 1307 1313 1319 1321 1327 1339 1345 1351 1361 1367 1373 1381 1385 1387 1391 1399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 19991399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 19991399 1403 1405 1409 1417 1423 1427 1429 1433 1439 1447 1451 1453 1459 1465 1469 1471 1481 1483 1487 1489 1493 1499 1511 1513 1517 1523 1531 1537 1543 1549 1553 1559 1565 1567 1571 1579 1583 1585 1591 1597 1601 1603 1607 1609 1613 1619 1621 1627 1637 1649 1651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 1999651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 1999651 1657 1663 1667 1669 1679 1685 1687 1693 1697 1699 1703 1709 1717 1721 1723 1727 1733 1739 1741 1745 1747 1753 1759 1765 1769 1777 1781 1783 1787 1789 1801 1807 1811 1823 1831 1843 1847 1853 1861 1865 1867 1871 1873 1877 1879 1885 1889 1891 1901 1907 1913 1921 1931 1933 1937 1939 1945 1949 1951 1961 1963 1973 1979 1985 1987 1991 1993 1997 1999

4

1 回答 1

1

您应该将条目翻转到筛子列表中。在第一个嵌套的 for 循环中，而不是prime[n]=true;你应该有prime[n]=!prime[n];

于 2013-08-13T01:37:13.900 回答