基于生成孿生素數算法的小型評測模型研究

孫金龍

摘要：孿生素數是指距離為2或1的相鄰素數。可以通過編寫程序的形式給出一定范圍內的孿生素數組數。而對于指定孿生素數生成的算法，需要判定程序的可行性與正確性。該文研究一個程序評測系統模型，當用戶提交了代碼以后，系統會自動對代碼進行編譯，運行，最后得出相應的結果，作為評測結果反饋給用戶。該模型用于校驗指定算法的正確性，減少程序評測中的工作量。該文重點研究基于生成孿生素數算法的小型評測模型。

關鍵詞：孿生素數；評測系統；JAVA

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2019）05-0089-04

Research on Small Evaluation Model Based on Generating Twin Prime Algorithms

SUN Jin-long

（School of Data Science and Software Engineering，Baoding University， Baoding 071000， China）

Abstract： There is a more basic number in mathematics than integer numbers， prime numbers. The reason why prime numbers are important is that any integer larger than 1 can be decomposed into the product of prime numbers， and this product is unique. Twin primes are two adjacent prime numbers whose distance is 2. （stipulates that two prime numbers adjacent to 1 are also twin primes）. The number of twins elements in a certain range can be given in the form of programming. For the algorithm of generating twin primes， it is necessary to determine the feasibility and correctness of the program.In order to fulfill the above requirements， we need a small evaluation model， which is similar to the program evaluation system. When the user submits the code， the system automatically compiles and runs the code， and finally obtains the corresponding results， which are fed back to the user as the evaluation results. This model is used to check the correctness of the specified algorithm and reduce the workload in program evaluation. This paper focuses on the small evaluation model based on the generating Twin Prime algorithm. The following discussion is made for this model.

Key words： twin prime number； evaluation system；JAVA

1 前言

1.1 評測系統的概念和應用場景

評測系統是在編程中用來評測程序執行結果正確性的系統，通過該系統對程序的代碼進行編譯和執行，之后系統使用預設結果和程序輸出結果進行比對，檢測程序的正確性。對于程序設計的初學者而言，設計出全面的測試數據是較為困難的，如果一組數據、一組數據的逐個測試算法執行結果的正確性，又十分的浪費時間，而且容易造成測試不準確的情況。另一方面，由于對測試數據的考慮不夠全面，在已完成的程序中往往有許多的邊界數據沒有考慮到，導致程序實質上是錯誤的，而程序設計者自己卻沒有察覺。因此算法評測系統用來檢測結果的正確性就非常方便了。該系統的技術理論依據是軟件工程方法學中的黑盒測試。研究目的主要是對算法進行自動化測試，校驗指定算法執行結果的正確性，減少程序評測中的工作量。本文以孿生素數算法作為切入點，旨在研究一個一般化的小型評測模型。

1.2 孿生素數問題的描述

孿生素數問題多見于ACM競賽中。是一類常見的具有代表性的算法，也是一個經典的數學問題。本文所述的孿生素數是指給出一百萬以內的數，以算法的形式計算出該數范圍內的全部孿生素數的組數（如10以內的孿生素數組為2和3，3和5，5和7共三組，則輸出結果為3）。因此需要生成一百萬條測試用例作為該算法的輸入準備。

1.3 孿生素數問題的評測過程

首先給出正確程序生成的全部測試用例，通過I/O流輸出到文件并且通過格式轉換將所有測試用例生成到數據庫中；

其次通過測試用例抽取程序從數據庫中隨機抽取五條包含正確結果的測試用例，并將待輸入的測試用例與正確結果分離，將分離的待輸入測試用例輸入到正在執行的孿生素數算法中，將正確結果以文件的形式存儲于本地計算機中，同時將待測算法執行結果輸出到單獨的文件中；

最終將正確答案文件內容與執行結果輸出文件內容通過比對程序進行比對并返回測試結果到文件中。

實現技術： I/O流，java反射機制，線程。

1.4 數據流圖

2 測試用例生成算法

2.1 功能描述

試用例生成算法的作用是生成正確的測試用例為評測系統的測試提供原始數據，生成的數據中包含一百萬條測試數據及其對應的正確結果。由于生成的數據量較大，該算法不僅應當保證結果的準確性，還需要注意盡可能降低算法的時間復雜度，以保證運行效率。

2.2 核心代碼

public static void main（String args[]）{

Scanner sc=new Scanner（System.in）；

int n=sc.nextInt（）；

int count=0；

try {

PrintStream out = new PrintStream（"f：//output.txt"）；//輸出到文件

while（n-->0）

{

int m=sc.nextInt（）；

count=0；

for（int i=1；i<=m；i++）

{

if（PrimeNumber（i））

{

if（PrimeNumber（i-1））

count++；

if（PrimeNumber（i-2））

count++；

}

}

System.setOut（out）；

System.out.println（count）；

}

} catch （Exception e） {

e.printStackTrace（）；

}

}

static boolean PrimeNumber（int n）{

if（n<=3）

return n>1；

if（（n-1）%6！=0&&（n+1）%6！=0）

return false；

int tem=（int）Math.sqrt（n）；

for（int j=5；j<=tem；j+=6）

if（n%j==0||n%（j+2）==0）

return false；

return true；

}

3 抽取算法

3.1 功能描述

抽取算法即針對數據庫中龐大的測試數據通過算法選擇某幾條測試用例作為待測程序的輸入。通過與數據庫的交互，獲得測試用例。

3.2 流程圖

3.3 核心代碼

public String[] GainTest（） {

//獲取數據庫連接并返回抽取的結果集

ResultSet rs = DBConnection（）；

try {

//獲取數據集中的正確答案

param = AquAns（rs）；

//獲取數據集中的正確結果

String[] temp = AquAns（rs）；

for（int i=0；i

System.setOut（out1）；//輸出到文件

System.out.println（temp[i]）；

}

} catch （Exception e） {

e.printStackTrace（）；

}

return param；

}

4 測試模型

4.1 功能描述

該部分是測試模型實現的核心。利用java反射機制，生成待測算法的class對象，啟動一個單線程執行該對象的main方法，在抽取算法中獲得的測試數據將通過標準輸入流輸入到待測試的孿生素數算法中，并將待測算法的輸出結果以文件的形式保存起來。

4.2 流程圖

4.3 核心代碼

static int cnt = 5；

static String[] temp=new String[cnt]；

ReadRecordByJDBC rr=new ReadRecordByJDBC（）；

String from = cnt+" "；

public void run（） {

temp = rr.GainTest（）；

for（int i=0；i

{

from+=temp[i]+" "；

}

try {

//將字符串轉化為輸入流

InputStream is = getStringStream（String.valueOf（from））；

System.setIn（is）；

//反射生成class對象

Class clazz = Class.forName（"com.oj.test.LuanShengSuShu"）；

//獲取該class對象的main方法

Method mainMethod = clazz.getMethod（"main"， String[].class）；

mainMethod.invoke（null，（Object）new String[]{""}）；

is.close（）；

} catch （Exception e） {

e.printStackTrace（）；

}

//輸出答案比較

new CompareTxTFile（）；

}

5 比對算法

5.1 功能描述

該算法主要作用即對從數據庫中獲得的正確結果與通過孿生素數測試獲得的結果以I/O流字符的形式逐行進行比對，并將評測結果一并輸出到測試結果文件中。

5.2 流程圖

6 測試

待測程序及測試結果

本節包含兩個待測程序，分別給出測試結果中包含的全部兩種情況。

待測程序1（輸出正確結果）

public class TwinPrime {

static int[] prime = new int[1000005]；

public static void main（String[] args） {

int i， j， flag， T， M；

for （i = 2； i <= 1000000； i++）

// *篩選偶數/利用篩選法求素數

if （i % 2 == 0 && i > 2）

prime[i] = 0；

else

prime[i] = 1；

for （i = 3； i <= （int） Math.sqrt（1000000）； i += 2）// 奇數

{

if （prime[i] == 1）

for （j = i + i； j < 1000000； j += i）

prime[j] = 0；

}

Scanner sc = new Scanner（System.in）；

try {

PrintStream out = new PrintStream（"f：//output.txt"）；

T = sc.nextInt（）；

while （T-- > 0） {

M = sc.nextInt（）；

for （i = M， flag = 0； i >= 2； i--）

if （（prime[i] == 1 && prime[i - 1] == 1）

|| （prime[i] == 1 && prime[i - 2] == 1））

flag++；

System.setOut（out）；

System.out.println（flag）；

}

} catch （FileNotFoundException e） {

e.printStackTrace（）；

}

}

}

評測正確結果：

待測程序2（評測出錯）

public class Test {

public static ArrayListprime=new ArrayList（）；

public static void main（String[]arg）{

int[] res=new int[1000005]；

int result=1；

res[3]=res[4]=1；

prime.add（2）；

prime.add（3）；

for（int i=5；i<1000005；i+=2）{

if（isPrime（i））{

prime.add（i）；

if（i-prime.get（prime.size（）-2）==2）{

result+=1；

}

}

res[i+1]=res[i]=result；

}

int num；

try {

PrintStream out = new PrintStream（"f：//output.txt"）；

Scanner in=new Scanner（System.in）；

num=in.nextInt（）；

for（int i=0；i

System.setOut（out）；

System.out.println（res[in.nextInt（）]+1）；

}

}catch （FileNotFoundException e） {

e.printStackTrace（）；

}

}

public static boolean isPrime（int num）{

for（int i=0；prime.get（i）*prime.get（i）<=num；i++）{

if（num%prime.get（i）==0）

return false；

}

return true；

}

}

參考文獻：

[1] 臧雙媛.C語言編程題在線評測系統的設計與研究[D].北京：北京交通大學，2017.

[2] 晏燕.在線編程評測系統設計與實現[D].長春：吉林大學，2017.

[3] 肖紅玉，藍榮祺，萬志強.在線評測教學輔助系統設計與應用[J].電子設計工程，2017，25（23）：11-15.

[4] 姚佳瑜.軟件測試中的測試用例及復用研究[J].數字技術與應用，2018，36（1）：58-59.

[5] 劉建亞.孿生素數猜想[J].數學通報，2014（1）.

[6] 林圍強.Java反射機制的研究[J].信息系統工程，2016（8）：109.

[7] 周文剛，劉了一.程序設計結果在線即時評測系統的設計與實現[J].周口師范學院學報，2018，35（5）：87-89.

【通聯編輯：謝媛媛】