问题标签 [sieve-of-atkin]

我基于Wikipedia 低效但清晰的伪代码编写了一个极其幼稚的 Atkin 筛子实现。我最初在 MATLAB 中编写了算法，它省略了 5 作为质数。我还用 Python 编写了算法，结果相同。

从技术上讲，我知道为什么5 被排除在外；在步骤 where n = 4*x^2 + y^2，n == 5 当 x == 1 和 y == 1 时。这只发生一次，所以 5 从素数翻转到非素数并且永远不会翻转回来。

为什么我的算法与 Wikipedia 上的算法不匹配？虽然我做了一些表面上的调整（例如，每次迭代只计算一次 x^2，在第一个方程中使用它时存储 mod(n, 12) 的值等），但它们不应该改变逻辑算法。

我阅读了几个与阿特金筛子 相关的讨论 ，但我不知道哪些差异在我的实现中造成了问题。

Python代码：

MATLAB代码

维基百科伪代码

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

这是代码：

和她的 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

I submitted this problem in spoj and this is showing runtime error(SIGABRT). It's working properly on my machine and on Ideone.com but showing error there. any reason? I am writing my code here: what I am trying to do is to calculate primes of order 10^8 and handling some operations on it. here is the problem link: http://www.spoj.com/problems/CPRIME

我一直在尝试学习生成素数的算法，我在维基百科上遇到了阿特金筛子。我几乎了解算法的所有部分，除了少数。以下是问题：

1. 下面的三个二次方程是如何形成的？4x^2+y^2、3x^2+y^2 和 3x^2-y2
2. 维基百科中的算法讨论了模 60，但我不明白在下面的伪代码中如何/在哪里使用它。
3. 这些提示 1、5、7 和 11 是如何找到的？

以下是来自维基百科的伪代码供参考：

我已经用 C++ 实现了自己的 Atkin 筛，它生成的素数很好，直到大约 860,000,000。在那里和更高的地方，程序开始返回几个复合材料，或者我认为。我在程序中有一个变量，用于计算找到的素数的数量，并且在 ~860,000,000 处，计数超过了应有的数量。我对照一个类似的埃拉托色尼筛子程序和几个互联网资源检查了我的计数。我是编程新手，所以这可能是一个愚蠢的错误。

无论如何，这里是：

我正在做欧拉项目，我遇到了这个问题。我在 VS 2013 中运行代码，程序由于溢出而崩溃。

这是我的方法：

此方法包括 2 种计算范围内所有素数之和的方法PRIME_LIMIT。第二种方法需要很长时间才能获得结果，并且可能需要一整天。第一种方法是使用阿特金的筛子，程序崩溃！

我的代码有什么错误吗？？请帮忙！

我正在练习编写针对空间或时间复杂度进行优化的算法。使用素数筛，您至少必须存储找到的所有素数的列表。似乎与找到的素数成比例的数据是这种算法可能使用的最少空间。

• 这个理由有效吗？
• 如何评估该算法的空间复杂度？

来自关于阿特金筛子的维基百科- 我不确定当素数数量超过此值时，筛子如何使用 O(n^1/2) 空间。这就是为什么看起来至少空间必须与素数的数量成比例的原因。我是否将可数数字与空间复杂度混淆了？

在这篇关于 Atkin 筛子的论文中，他们的算法打印“最多为 N 的素数......这里的“内存”不包括打印机使用的纸张。” 这似乎是对空间的不公平计算。

• 我希望澄清这应该如何/实际上是客观地衡量的。

我的代码可以给出大多数素数，但它仍然包含 1 并遗漏了一些数字：23 和 47（在计算 100 以下的素数时）。出于某种原因，它包括 91，任何想法为什么？我一直在使用维基百科的阿特金筛子说明。

我的代码如下：

欢迎任何有关优化筛子的建议。谢谢

我想知道是否有人对我可以做些什么来提高代码的运行速度有任何建议。我写了一个Sieve of Atkin函数，它返回一个包含所有素数的向量[2, max]。

这是我的代码。

我有几个关于我可以做的更好的问题，以优化这个功能。

我将筛子数组初始化为布尔值的动态数组，以便它们都默认为false，让筛子像这样动态是更快还是应该将其保留为普通数组？

在算法处理后，我使用 for 循环将素数存储在向量中，是否有更快的方法可以找到筛子中的所有素数以将它们存储在向量中？

欢迎任何其他提示、技巧、提示或代码，非常感谢，谢谢。

只是为了好玩，我试图从这个 StackOverflow 答案中实现伪代码，用于 C++ 中高度分解的 Eratosthenes 筛。我不明白为什么我的代码会同时返回素数和非素数。我是否错误地实现了这些 for 循环？我应该改用while循环吗？我怀疑我没有正确增加 for 循环。任何帮助将不胜感激。我花了几个小时试图找出这个缺陷。

GordonBGood 的伪代码作为注释插入，我使用了所有相同的变量名。